MỞ ĐẦU Ngày nay cùng với việc phát triển của Khoa Học Công Nghệ thì lượng dữ liệu ngày càng trở nên lớn hơn, khai thác đươ ̣c những thông tin có ích từ lươ ̣ng dữ liê ̣u khổ n g lồ như vâ ̣y đang là vấn đề lớn đặt ra trong thực tiễn cuộc sống. Khai phá dữ liệu là một trong những lĩnh vực nghiên cứu của khoa học máy tính hiện nay đang được phát triển rất mạnh mẽ. Nó kết hợp giữa học máy, công nghệ cơ sở dữ liệu và một số chuyên ngành khác để tìm ra những tri thức, bao gồm cả các thông tin dự báo, từ những cơ sở dữ liệu lớn. Phân lớp dữ liệu được coi là một trong những vấn đề nghiên cứu mở rộng hiện nay trong Khai phá dữ liệu, hiện nay có rất nhiều dữ liệu thực tế lớn cần được phân lớp như: Việc khai thác thông tin về nhu cầu mua hàng dành cho những người bán hàng, hoặc các khả năng rủi ro trong việc cho vay tiền ở ngân hàng, hoặc việc cần phải phân biệt những người bị bệnh hoặc không bị bệnh trong một lớp dữ liệu của bệnh viện….
Như vậy việc phân tích được thông tin rất quan trọng, nhưng dữ liệu thực tế rất lớn và có rất nhiều lớp khác nhau, vậy bài toán được đặt ra ở đây là làm thế nào để phân loại được những lớp dữ liệu khác nhau càng nhiều càng tốt với độ chính xác cao. Như việc phân tích một bệnh ung thư, bệnh được chia làm nhiều giai đoạn, giờ đây điều quan tâm không những là việc xác định người bị bệnh và người không bị bệnh nữa mà còn là việc quan tâm xem người bị bệnh đang ở giai đoạn nào. Với một dữ liệu ung thư nếu xác định được giai đoạn bệnh của bệnh nhân thì khả năng những giai đoạn mới đầu là có thể được chữa khỏi, vì vậy việc đa phân lớp sẽ trở thành rất quan trọng trong việc phân lớp dữ liệu. Yêu cầu của một bài toán đa phân lớp đó là làm thế nào phân lớp dữ liệu thành nhiều lớp đạt hiệu quả cao nhất ở khả năng dự đoán những dữ liệu mới vào đúng lớp dữ liệu một cách chính xác nhất.
Hiện nay có rất nhiều thuật toán phân lớp như thuật toán Support vector machines (SVM) thuật toán phân lớp bằng Học cây quyết định, mô hình Mạng lan truyền ngược (Neural Network)[8],… và có nhiều kết quả đạt được trong việc sử dụng các mô hình phân lớp này vào việc đa phân lớp[8,11,14]. Nhưng vấn đề tìm kiếm một phương pháp đủ tốt đáp ứng nhu cầu cần phải phân tích dữ liệu ra nhiều lớp khác nhau vẫn là một vấn đề hiện nay cần nghiên cứu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Luận văn này tập trung tìm hiểu, xây dựng mô hình đa phân lớp mới bằng việc kết hợp một thuật toán phân lớp SVM với kĩ thuật đa phân lớp One agaist all (OAA) nhằm thực hiện đa phân lớp một tập dữ liệu. Luận văn cũng tập trung vào việc sử dụng giải thuật di truyền (GA) để tối ưu các tham số của hàm nhân Kernel của SVM phục vụ cho việc đa phân lớp nhằm tăng độ chính xác khi phân lớp của mô hình[10].
Nội dung chính của luận văn được tổ chức thành 4 chương có nội dung được mô tả như dưới đây. Thuật toán phân lớp SVM. Chương này giới thiê ̣u cơ bản về vấn đề phân lớp, các bước trong phân lớp và những yêu cầu trong vấn đề phân lớp. Chương này tập trung vào một thuật toán phân lớp SVM, nghiên cứu kỹ thuật đa phân lớp nhằm xây dựng mô hình đa phân lớp với SVM Chƣơng 2.
Giải thuật di truyền. Chương này trin ̀ h bày về giải thuật di truyền, tìm hiểu và áp dụng giải thuật nhằm tối ưu các giá trị Chƣơng 3. Mô hình tối ƣu đa phân lớp SVM. Chương này trin ̀ h bầ y viê ̣c xây dựng một mô hình đa phân lớp dựa vào giải thuật di truyền, kĩ thuật One against all và SVM.
Đề cập đến việc tìm kiếm các Kernel tốt cho mô hình bằng việc sử dụng giải thuật di truyền để tối ưu các tham số của Kernel. Xây dựng chƣơng trình mô phỏng. Chương này sử dụng những lý luận ở trên kết hợp với MATLAB để xây dựng mô hình phân lớp phân tích trên một số tập dữ liệu cụ thể nhằm thu được các kết quả để đánh giá mô hình mới xây dựng (GA&SVM) so với mô hình đa phân lớp SVM. Phần kết luận tổng kết những kết quả đạt được của luận văn và hướng phát triển nghiên cứu tiếp theo.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Chƣơng 1 - THUẬT TOÁN PHÂN LỚP VỚI SVM 1.Giới thiệu chung về phân lớp 1.Khái niệm cơ bản Một nhà nghiên cứu về y học muốn phân tích dữ liệu về bệnh ung thư phổi để dự đóan trước một trong ba phương pháp điều trị đặc biệt dành cho bệnh nhân, nhân viên ngân hàng khi xem xét quyết định cho vay, họ cần phải phân tích xem hồ sơ vay nào là “an toàn”, cái nào là “rủi ro”. Việc phân tích dữ liệu được gọi là phân lớp (Classification), trong đó một mô hình (Classifier) được xây dựng để dự đoán các nhãn như là “an tòan”, “rủi ro” của dữ liệu cho vay, “ phương pháp A”, “phương pháp B”, “phương pháp C” của dữ liệu y học.[5] Mục đích của phân lớp là dự đoán giá trị lớp của thuộc tính đích dựa trên các giá trị thuộc tính đầu vào. Ta phải dựa vào các mối quan hệ giữa các đối tượng để tìm ra sự giống nhau giữa các đối tượng theo một độ đo nào đó đặc trưng cho lớp.1 Mô hình phân lớp 1.Quá trình phân lớp Gồm hai bước: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Bước 1: Xây dựng mô hình từ tập dữ liệu huấn luyện Bước 2: Sử dụng mô hình: Kiểm tra tính đúng đắn của mô hình và dùng nó để phân lớp dữ liệu mới Xây dựng mô hình Sử dụng mô hình để dự báo Dữ liệu Dữ liệu Dữ liệu Bộ phân loại (mô kiểm tra chưa biết huấn luyện hình ) Hình 1.Quá trình phân lớp 1.Xây dựng mô hình - Mỗi bộ/mẫu dữ liệu được phân vào lớp đã xác định trước - Lớp của bộ/mẫu dữ liệu được chỉ ra trong thuộc tính nhãn lớp của bộ/mẫu dữ liệu đó. - Tập dữ liệu được dùng để xây dựng mô hình gọi là tập dữ liệu huấn luyện.
- Mô hình được xây dựng có thể là các luật phân lớp, cây quyết định hoặc có thể là các công thức toán học, bộ tham số ….Sử dụng mô hình - Phân lớp cho các đối tượng trong tương lai hoặc các đối tượng chưa biết. - Đánh giá độ chính xác của mô hình + So sánh các nhãn lớp đã biết của các bộ trong tập dữ liệu kiểm tra với kết quả phân lớp của mô hình + Độ chính xác là tỉ lệ phần trăm của các bộ trong tập dữ liệu kiểm tra được phân lớp đúng mô hình - Tập dữ liệu phải có cùng khuôn dạng và độc lập với tập dữ liệu huấn luyện LUAN VAN CHAT LUONG download : add luanvanchat@agmail.Các yêu cầu đối với bàn toán phân lớp Các phương pháp phân lớp thường đòi hỏi một số yêu cầu sau: - Tính tuyến tính: Với các tập dữ liệu nhỏ mà số lượng các đối tượng ít thì các thuật toán có thể giải quyết tốt, nhưng trên thực tế có những cơ sở dữ liệu lớn có thể có hàng ngàn, hàng triệu đối tượng. Khi đó phân lớp có thể dẫn đến kết quả không như mong muốn hoặc tốn rất nhiều thời gian. - Khả năng làm việc với nhiều loại dữ liệu khác nhau: Dữ liệu không đơn thuần chỉ là các con số, mà còn có nhiều kiểu dữ liệu.
Vì thế, các ứng dụng có thể yêu cầu phân lớp với nhiều dạng dữ liệu như nhị phân, dữ liệu phân loại, dữ liệu hỗn hợp theo nhiều kiểu. - Tối thiểu các tham số đầu vào: các tham số thường rất khó xác định, đặc biệt với các tập dữ liệu có các đối tượng nhiều chiều. Điều này gây khó khăn cho người sử dụng và ảnh hưởng tới chất lượng của các lớp. - Khả năng làm việc với các dữ liệu nhiễu.
Hầu hết các dữ liệu thực đều có dữ liệu không đầy đủ, không biết rõ hoặc dữ liệu lỗi. Một số thuật toán rất nhạy cảm với các dữ liệu như vậy và có thể làm giảm khả năng phân lớp của chúng. - Không phụ thuộc vào thứ tự của các bản ghi đầu vào. Với cùng một tập dữ liệu, khi biểu diễn với thứ tự khác nhau, một số thuật toán có thể tạo ra những lớp khác nhau.
Vì vậy yêu cầu thuật toán không phụ thuộc vào thứ tự đầu vào của dữ liệu là một yêu cầu hết sức quan trọng. - Khả năng làm việc với dữ liệu nhiều chiều: với lượng dữ liệu lớn, lượng thông tin càng ngày càng thay đổi thì một cơ sở dữ liệu có thể có nhiều chiều hoặc nhiều thuộc tính. Các thuật toán có thể xử lý tốt với dữ liệu ít chiều xong lại không tỏ ra hiệu quả với dữ liệu nhiều chiều. Đây cũng là một thách thực lớn trong phân lớp các đối tượng dữ liệu trong không gian nhiều chiều.
- Phân lớp các ràng buộc. Các ứng dụng trong thực tế có thể phải thực hiện phân lớp với nhiều ràng buộc. Nhiệm vụ của phân lớp là phải tìm một nhóm dữ liệu sao cho phân lớp tốt nhất thỏa mãn các điều kiện ràng buộc. - Tính có thể hiểu được và khả năng sử dụng được.
Người sử dụng mong rằng có thể hiểu được, nhận biết được và sử dụng được các lớp sau khi chia. Điều đó đòi hỏi các lớp sau khi được phân lớp phải có ý nghĩa và đem lại ứng dụng. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Với những yêu cầu trên, thật khó để có thể tìm được một thuật toán đáp ứng được tất cả các yêu cầu. Vì vậy đây luôn là một thách thức lớn đối với lĩnh vực khai phá dữ liệu.Kỹ thuật phân lớp SVM(Support vector machines) SVM là phương pháp học máy cho phép phân lớp các đối tượng ra thành hai lớp.
Mặc dù các đối tượng cần phân lớp hết sức phong phú từ tranh ảnh, âm thanh, đồ thị…, nhưng ở đây tôi chỉ xem xét các đối tượng là các vector thực với số chiều hữu hạn 2.SVM tuyến tính 2.Các bộ phận phân lớp tuyến tính Giả sử m=2, hay mỗi đối tượng chỉ là một vector hai chiều x = (x1, x2). Mỗi đối tượng như vậy có thể được biểu diễn bởi một điểm trên mặt.