Tài liệu Giáo trình học máy

1 MỤC LỤC MỤC LỤC.................................................................................................................. 1 Chương 1. KHÁI NIỆM HỌC MÁY...............................................................................4 1.1. Khái niệm học máy............................................................................................4 2.1.1. Khái niệm học....................................................................................................4 2.1.2. Học máy.............................................................................................................4 2.1.3. Một số khái niệm...............................................................................................5 1.2. Các phương pháp học máy.................................................................................6 1.3. Ứng dụng của học máy......................................................................................7 Chương 2. HỌC CÂY QUYẾT ĐỊNH.........................................................................8 2.1. Mở đầu.............................................................................................................. 8 2.2. Bài toán phân lớp và dự báo...............................................................................8 2.2.1. Phân lớp và dự báo.............................................................................................9 2.2.2. Chuẩn bị dữ liệu cho phân lớp và dự báo........................................................11 2.2.3. So sánh các phương pháp phân lớp..................................................................12 2.3. Khái niệm về bảng quyết định và cây quyết định...............................................12 2.3.1. Bảng quyết định...............................................................................................12 2.3.2. Cây quyết định.................................................................................................14 2.4. Thuật toán học cây quyết định..........................................................................15 2.4.1. Thuật toán ID3 học cây quyết định..................................................................15 2.4.2. Lựa chọn thuộc tính tốt nhất tại mỗi nút..........................................................16 2.4.3. Ví dụ minh họa.................................................................................................18 2.4.4. Các đặc điểm thuật toán học cây quyết định....................................................20 2.4.5. Vấn đề quá vừa dữ liệu....................................................................................20 2.4.6. Sử dụng thuộc tính có giá trị liên tục...............................................................22 Chương 3. HỌC PHÂN LOẠI BAYES ĐƠN GIẢN..................................................24 3.1. Phương pháp phân loại Bayes đơn giản.............................................................24 3.2. Vấn đề tính xác suất trên thực tế.......................................................................27 3.3. Ứng dụng trong phân loại văn bản tự động........................................................28 2 Chương 4. HỌC DỰA TRÊN VÍ DỤ: THUẬT TOÁN K LÁNG GIỀNG GẦN NHẤT 30 4.1. Nguyên tắc chung............................................................................................30 4.2. Phương pháp k-láng giềng gần nhất..................................................................31 4.3. Một số lưu ý cho thuật toán k-NN.....................................................................32 4.3.1. Các độ đo khoảng cách và độ tương tự............................................................32 4.3.2. Sử dụng trọng số cho các hàng xóm................................................................33 4.3.3. Ảnh hưởng của thuộc tính tới thuật toán.........................................................33 Chương 5. HỌC MẠNG NƠRON NHÂN TẠO........................................................35 5.1. Các khái niệm cơ bản về mạng nơron................................................................35 5.1.1. Sơ lược về mạng nơron....................................................................................35 5.1.2. Mô hình nơron.................................................................................................39 5.1.3. Kiến trúc mạng nơron (Network Architectures)..............................................44 5.1.4. Các hình trạng của mạng nơron (Network topologies)....................................46 5.1.5. Huấn luyện mạng nơron (học mạng nơron).....................................................48 5.1.6. Hàm mục tiêu (Objective Function)................................................................49 5.2. Mạng cảm ứng (Perceptron).............................................................................50 5.2.1. Kiến trúc mạng cảm ứng..................................................................................50 5.2.2. Mạng cảm ứng một nơron................................................................................51 5.2.3. Mạng cảm ứng nhiều nơron.............................................................................53 5.2.4. Thuật toán tập huấn mạng cảm ứng.................................................................54 5.2.5. Hạn chế của mạng cảm ứng.............................................................................58 Chương 6. HỌC LUẬT KẾT HỢP............................................................................60 6.1. Các khái niệm cơ bản.......................................................................................60 6.1.1. Cơ sở dữ liệu giao tác......................................................................................60 6.1.2. Tập mục thường xuyên và luật kết hợp...........................................................62 6.1.3. Bài toán khai phá luật kết hợp.........................................................................64 6.2. Khai phá tập mục thường xuyên.......................................................................64 6.2.1. Các cách tiếp cận khai phá tập mục thường xuyên..........................................64 6.2.2. Thuật toán Apriori............................................................................................66 6.2.3. Thuật toán FP-growth......................................................................................70 3 6.3. Một số mở rộng bài toán khai phá tập mục thường xuyên...................................76 4 Chương 1. KHÁI NIỆM HỌC MÁY 1.1. Khái niệm học máy 2.1.1. Khái niệm học Theo Herbert Simon: ‘Học được định nghĩa như là bất cứ sự thay đổi nào trong một hệ thống cho phép nó tiến hành tốt hơn trong lần thứ hai khi lặp lại cùng một nhiệm vụ hoặc với một nhiệm vụ khác rút ra từ cùng một quần thể các nhiệm vụ đó’ Định nghĩa này mặc dù ngắn nhưng đưa ra nhiều vấn đề liên quan đến việc phát triển một chương trình có khả năng học. Học liên quan đến việc khái quát hóa từ kinh nghiệm: hiệu quả thực hiện của chương trình không chỉ cải thiện với ‘việc lặp lại cùng một nhiệm vụ’ mà còn với các nhiệm vụ tương tự. Vì những lĩnh vực đáng chú ý thường có khuynh hướng là to lớn, nên các chương trình học - CTH (learner) chỉ có thể khảo sát một phần nhỏ trong toàn bộ các ví dụ có thể; từ kinh nghiệm hạn chế này, CTH vẫn phải khái quát hóa được một cách đúng đắn những ví dụ chưa từng gặp trong lĩnh vực đó. Đây chính là bài toán quy nạp (induction), và nó chính là trung tâm của việc học. Trong hầu hết các bài toán học, dữ liệu luyện tập sẵn có thường không đủ để đảm bảo đưa ra được một khái quát hóa tối ưu, cho dù CTH sử dụng giải thuật nào. Vì vậy, các giải thuật học phải khái quát hóa theo phương pháp heuristic, nghĩa là chúng sẽ chọn một số khía cạnh nào đó mà theo kinh nghiệm là cho hiệu quả trong tương lai để khái quát. Các tiêu chuẩn lựa chọn này gọi là thiên lệch quy nạp (inductive bias). Có nhiều nhiệm vụ học (learning task) khác nhau. Ở đây chỉ trình bày nhiệm vụ học quy nạp (inductive learning), đây là một trong những nhiệm vụ học cơ bản. Nhiệm vụ của CTH là học một khái quát (generalization) từ một tập hợp các ví dụ. Học khái niệm (concept learning) là một bài toán học quy nạp tiêu biểu: cho trước một số ví dụ của khái niệm, chúng ta phải suy ra một định nghĩa cho phép người dùng nhận biết một cách đúng đắn những thể hiện của khái niệm đó trong tương lai. 2.1.2. Học máy Học máy (Machine learning) là một lĩnh vực của trí tuệ nhân tạo liên quan đến việc nghiên cứu và xây dựng các kĩ thuật cho phép các hệ thống "học" tự động từ dữ liệu để giải quyết những vấn đề cụ thể: Học từ dữ liệu để trích lọc ra các tri thức 5 (khai phá dữ liệu); Học từ dữ liệu trong quá khứ để dự báo dữ liệu trong tương lai (dự báo). Một số ví dụ về học máy:  Học cách phân loại thư điện tử: Chương trình học cách phân loại thư điện từ xem có phải thư rác (spam) hay không và tự động xếp thư vào thư mục tuơng ứng.  Học cách đánh cờ: Chương trình có thể quan sát các ván cờ cùng với kết quả để cải thiện khả năng chơi cờ và tăng các ván thắng trong tương lai.  Học nhận dạng các ký tự: Dữ liệu để học là ảnh chụp các ký tự cùng với mã ASCII của ký tự đó. Quá trình học cho phép chương trình tăng độ chính xác khi phân biệt các ảnh chụp sau đó. Học máy có liên quan lớn đến thống kê, vì cả hai lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhưng khác với thống kê, học máy tập trung vào sự phức tạp của các giải thuật trong việc thực thi tính toán. Nhiều bài toán trong thực tế được xếp vào loại bài toán NP-khó mà máy tính không xử lý được, một trong những mục tiêu của học máy là nghiên cứu các giải thuật suy luận xấp xỉ hoặc kinh nghiệm (heuristic) để giải quyết bài toán trong thời gian đa thức, nhờ đó có thể xử lý bằng máy tính. Học máy và khai phá dữ liệu là hai khái niệm hay bị nhầm lẫn. Hai lĩnh vực này nhìn chung gần với nhau và đôi khi dùng chung nhiều phuơng pháp, công cụ nhưng khác biệt chính là ở mục tiêu:  Khai phá dữ liệu: Mục tiêu là tìm kiếm những tri thức hoàn toàn mới, có ích, tiềm ẩn trong nguồn dữ liệu.  Học máy: Dự đoán một số thông tin của dữ liệu dựa trên những đặc tính đã biết. 2.1.3. Một số khái niệm  Mẫu hay ví dụ là tên gọi đối tượng cần phân loại. Ví dụ khi lọc thư rác, mỗi thư được gọi là một mẫu hay một ví dụ. Mẫu thường được mô tả bằng một tập các thuộc tính (hay đặc trưng). Ví dụ: trong bài toán chuẩn đoán bệnh, thuộc tính là các triệu chứng của người bệnh và các tham số khác như cân nặng, huyết áp. 6  Nhãn phân loại thể hiện loại đối tượng cần dự đoán. Ví dụ: với bài toán phân loại thư rác, nhãn phân loại có thể là “rác” hay “bình thường”. Trong giai đoạn học, thuật toán được cung cấp cả tập dữ liệu huấn luyện và nhãn phân loại. Trong giai đoạn dự đoán, thuật toán chỉ được cung cấp mẫu không nhãn và cần xác định nhãn cho những mẫu này. 1.2. Các phương pháp học máy  Học có giám sát hay học có thầy (supervised learning): Trong giai đoạn học (huấn luyện), thuật toán học xây dựng hàm đích (hàm dự báo, phân loại) dựa trên các tập mẫu cùng với nhãn phân loại tương ứng (tập dữ liệu huấn luyện). Trong giai đoạn dự báo (phân loại), từ tập mẫu không có nhãn phân loại (tập dữ liệu kiểm tra), hàm đích đưa ra nhãn phân loại (dự báo) của các mẫu này. Quá trình học được biểu diễn bằng sơ đồ sau: Mẫu kiểm tra (không nhãn) Mẫu huấn luyện (có nhãn) Thuật toán học máy Hàm đích (dự báo, phân loại) Mẫu kiểm tra (không nhãn) Các chủ đề nghiên cứu (hay các công cụ) trong học có thầy bao gồm:  Học cây quyết định ứng dụng trong phân loại và dự đoán  Học mạng nơ ron nhân tạo ứng dụng trong phân loại và dự đoán  Học phân lớp Bayes đơn giản  Học máy véc tơ hỗ trợ SVM (Suppor Vector Machines)  Học phân lớp sử dụng công cụ lý thuyết tập thô (rough set theory)  Học không có giám sát hay học không có thầy (unsupervised learning): Là phương pháp học chỉ dựa trên các tập mẫu mà không có nhãn phân loại đi kèm. Hệ thống học phải tự phám phá các đặc trương, các mỗi tương quan của các mẫu học một cách tự động. 7 Các chủ đề nghiên cứu (hay các công cụ) trong học có thầy bao gồm:  Học phân cụm (Clustering), thuật toán phân cụm K-means  Học luật kết hợp (Association Rule Learning).  Học dựa trên ví dụ: Phương pháp k-láng giềng gần nhất (k-Nearest Neighbors, kNN).  Học mạng nơ ron nhân tạo. 1.3. Ứng dụng của học máy Có rất nhiều ứng dụng thực tế khác nhau của học máy trong nhiều lĩnh vực, sau đây là một số ứng dụng điển hình:  Nhận dạng: Nhận dạng ký tự, phát hiện và nhận dạng mặt người, nhận dạng tiếng nói.  Y khoa: Chuẩn đoán y tế, dự đoán người bệnh dựa trên triệu chứng quan sát được. Ứng dụng trong tin sinh học như phân tích gen, phân tích chuỗi DNA…  Kinh doanh: Phân loại khách hàng, dự đoán chỉ số thị trường chứng khoán, giá cả tiêu dùng…  Đào tạo: Dịch tự động…  Giải trí: trò chơi… 8 Chương 2. HỌC CÂY QUYẾT ĐỊNH 2.1. Mở đầu Học cây quyết định là một trong phương pháp học máy tiêu biểu có nhiều ứng dụng trong phân lớp và dự báo. Mặc dù độ chính xác của phương pháp này không thật cao so với những phương pháp được nghiên cứu gần đây, học cây quyết định vẫn có nhiều ưu điểm như đơn giản, dễ lập trình, và cho phép biểu diễn hàm phân loại dưới dạng dễ hiểu, dễ giải thích cho con người. Phương pháp này thường được dùng như phương pháp mở đầu để minh họa cho kỹ thuật học bộ phân lớp từ dữ liệu. Phương pháp học cây quyết định được sử dụng cho việc học các hàm phân lớp từ dữ liệu huấn luyện, trong đó cây quyết định được sử dụng làm biểu diễn xấp xỉ của hàm phân lớp, tức là hàm có đầu ra là các giá trị rời rạc. Như đã nói ở trên, phương pháp học này thuộc loại học có giám sát (học có thầy). Phần này sẽ giúp người đọc làm quen với khái niệm cây quyết định, đồng thời giới thiệu một số thuật toán học cây quyết định bao gồm ID3 và C4.5. 2.2. Bài toán phân lớp và dự báo Cơ sở dữ liệu có nhiều thông tin bị che lấp có thể được sử dụng để ra các quyết định thông minh. Phân lớp và dự báo là hai hình thức học từ dữ liệu được sử dụng để rút ra những mô hình miêu tả lớp dữ liệu quan trọng hoặc dự báo xu thế dữ liệu trong tương lai. Trong khi phân lớp dự đoán các nhãn lớp đã được xác định rõ ràng (rời rạc) thì mô hình dự báo thực hiện chức năng trên những giá trị liên tục. Lấy ví dụ, một mô hình phân lớp được xây dựng để phân loại ứng dụng cho vay ngân hàng là an toàn hay mạo hiểm, trong khi một mô hình dự báo được xây dựng để dự báo lượng thiết bị máy tính được mua bởi các khách hàng tiềm năng dựa vào thu nhập và nghề nghiệp của họ. Nhiều phương pháp phân lớp và dự báo đã được giới thiệu bởi các nhà nghiên cứu trong các lĩnh vực học máy, hệ chuyên gia, thống kê…. Hầu hết các thuật toán sử dụng bộ nhớ thường trú, nên chỉ áp dụng với dữ liệu có kích thước nhỏ. Gần đây những nghiên cứu khai phá dữ liệu đã phát triển những kỹ thuật phân lớp và dự báo có khả năng làm chủ được dữ liệu có kích thước lớn, thường trú trên đĩa. Những kỹ thuật này thường liên quan đến xử lý song song và phân tán. 9 2.2.1. Phân lớp và dự báo Phân lớp dữ liệu là một quá trình gồm hai bước, hình 3.1. Trong bước thứ nhất, một mô hình được xây dựng để miêu tả một tập các lớp dữ liệu hay các khái niệm đã định trước. Mô hình này được xây dựng bằng cách phân tích các bản ghi cơ sở dữ liệu được mô tả bằng những thuộc tính. Mỗi bản ghi được xem như thuộc về một lớp được định nghĩa trước, vì được quyết định bằng một trong những thuộc tính nên gọi là thuộc tính nhãn lớp. Trong phạm vi phân lớp, các bản ghi dữ liệu cũng được xem là những ví dụ, mẫu hay đối tượng. Việc phân tích các bản ghi dữ liệu để xây dựng mô hình chung hình thành nên tập dữ liệu huấn luyện. Tập huấn luyện hình thành từ các bản ghi riêng biệt cũng xem như một mẫu huấn luyện và được lựa chọn ngẫu nhiên. Vì nhãn lớp của mỗi mẫu huấn luyện được cung cấp trước nên bước này được hiểu như là học có giám sát (tức là, việc học một mẫu là “được giám sát” trong đó nói lên mỗi mẫu huấn luyện thuộc về lớp nào). Phương pháp này đối lập với học không giám sát (phân cụm), trong đó nhãn lớp của mỗi mẫu huấn luyện là chưa biết và số lượng hoặc tập các lớp có thể cũng không biết trước. Thông thường, mô hình đã học được biểu diễn dưới dạng quy tắc phân lớp cây quyết định, hoặc công thức toán học. Lấy ví dụ, cho một cơ sở dữ liệu về thông tin tiền gửi của khách hàng, quy tắc phân lớp có thể được học để phân biệt khách hàng có loại tiền gửi được đánh giá tốt hay rất tốt (hình 2.1 a). Quy tắc có thể được sử dụng để phân loại các mẫu dữ liệu về sau, cũng như cung cấp những hiểu biết tốt hơn về nội dung của cơ sở dữ liệu. Trong bước thứ hai (hình 2.1 b), mô hình được sử dụng để phân lớp. Đầu tiên chúng ta phải đánh giá tính chính xác của mô hình dự báo. Có một kỹ thuật đơn giản để làm việc này đó là sử dụng một tập thử gồm các mẫu đã được gán nhãn, những mẫu này được lựa chọn ngẫu nhiên và độc lập với những mẫu huấn luyện. Độ chính xác của một mô hình trên tập thử là tỷ lệ phần trăm của các mẫu trong tập thử được phân lớp chính xác bằng mô hình đó. Với mỗi mẫu thử, nhãn lớp đã biết được so sánh với nhãn lớp mà mô hình dự báo cho mẫu đó. 10 Thuật Thuậttoán toán phân phânlớp lớp Dữ liệu đào tạo Tên (a) Tuổi Sandy Jones Bill Lee Coutnay fox Susan Lake Claire Phips … Thu nhập Đ.giá tiền gửi <=30 <=30 31…40 >40 31…40 …. thấp thấp cao trung bình trung bình … tốt rất tốt rất tốt tốt tốt … Nếu tuổi = “31..40” và thu nhập = “cao” đánh giá tiền gửi= “rất tốt” Quy tắc phân lớp Dữ liệu đào tạo (b) Tên Frank Jones Sylvia Crest Anne Yee … Tuổi > 40 <=30 31…40 …. Quy tắc phân lớp Dữ liệu mới Thu nhập Sự tín nhiệm cao thấp cao … tốt tốt rất tốt … John Henri, 31…40,high Đánh giá tiền gửi? rất tốt Hình 2.1 tiến trình phân lớp dữ liệu Nếu độ chính xác của mô hình được xem là chấp nhận được, thì nó có thể được sử dụng về sau để phân lớp những bản ghi dữ liệu hoặc các đối tượng mà chúng ta chưa biết nhãn lớp. Lấy ví dụ, quy tắc phân lớp đã học được từ việc phân tích dữ liệu khách hàng đã tồn tại có thể được sử dụng để dự báo loại tiền gửi của khách hàng mới hoặc khách hàng về sau (hình 2.1 a ). “Dự báo khác biệt với phân lớp ở chỗ nào?”. Dự báo có thể xem như việc xây dựng và sử dụng một mô hình để đánh giá một lớp ví dụ chưa được gán nhãn, hoặc để đánh giá giá trị hay khoảng giá trị của một thuộc tính trong một ví dụ đã cho có thể có. Theo cách này, phân lớp và hồi quy là hai loại quan trọng của dự báo vấn đề, phân lớp được sử dụng để dự báo những giá trị rời rạc hoặc dùng vào việc chỉ tên, trong khi hồi quy được sử dụng để dự báo những giá trị liên tục hoặc đã được sắp xếp. Tuy nhiên, theo quan điểm của chúng ta, việc sử dụng dự báo để tiên đoán những nhãn lớp như là phân lớp, và sử dụng dự báo để dự đoán những giá trị liên tục (tức là sử dụng kỹ thuật hồi quy) vẫn hay được sử dụng hơn. Quan điểm này thường cũng được chấp nhận trong khai phá dữ liệu. 11 Phân lớp và dự đoán có nhiều ứng dụng bao gồm chuẩn đoán y học, dự báo hiệu suất, lựa chọn thị trường … 2.2.2. Chuẩn bị dữ liệu cho phân lớp và dự báo Các bước tiền xử lý dữ liệu sau đây có thể được áp dụng với dữ liệu để giúp cải thiện độ chính xác, tăng tính hiệu quả và sự mềm dẻo của phân lớp và dự báo. Làm sạch dữ liệu (data cleaning): Bước này liên quan đến tiền xử lý dữ liệu để loại bỏ hay giảm nhiễu (ví dụ, áp dụng kỹ thuật làm mịn), xử lý những giá trị bị mất (chẳng hạn, bằng cách thay thể một giá trị bị mất bằng giá trị chung nhất đã tìm thấy của thuôc tính, hoặc bằng giá trị có khả năng đúng nhất dựa vào thống kê). Mặc dù hầu hết các thuật toán phân lớp đều có vài cơ chế để kiểm soát nhiễu và dữ liệu mất, bước này có thể làm giảm sự phức tạp trong quá trình học và nâng cao độ chính xác của mô hình thu được. Phân tích liên quan: Một số thuộc tính trong dữ liệu có thể không liên quan đến công việc phân lớp hoặc dự báo. Lấy ví dụ, dữ liệu ghi ngày trong tuần của một ứng dụng cho vay ngân hàng được đưa ra là không liên quan đến sự thành công của ứng dụng. Hơn thế nữa, một số thuộc tính có thể dư thừa. Vì vậy, phân tích liên quan có thể được thực hiện trên dữ liệu với mục đích loại bỏ những thuộc tính không có quan hệ hoặc dư thừa đối với quá trình học. Trong học máy, bước này được biết đến như lựa chọn đặc điểm. Việc học sẽ chậm đi và có thể bị lệch hướng nếu không có bước này. Trường hợp lý tưởng, thời gian sử dụng vào việc phân tích liên quan, cộng với thời gian sử dụng vào việc học trên kết quả của việc đã giảm các thuộc tính sẽ nhỏ hơn thời gian sẽ sử dụng để học trên dữ liệu gốc. Vì thế, việc phân tích này có thể giúp tăng hiệu quả phân lớp và sự mềm dẻo. Biến đổi dữ liệu: Dữ liệu có thể được tổng quát hóa lên mức khái niệm cao hơn. Thứ bậc khái niệm có thể được sử dụng cho mục đích này. Điều này đặc biệt hữu ích khi thuộc tính có kiểu dữ liệu liên tục. Lấy ví dụ, thuộc tính lợi nhuận có dữ liệu kiểu số có thể được tổng quát thành những khoảng rời rạc là cao, thấp, trung bình. Tương tự, đối với những thuộc tính có giá trị để chỉ tên, như “phố” có thể được tổng quát hóa thành khái niệm cao hơn ở mức “thành phố”. Vì tổng quát hóa nén dữ liệu huấn luyện gốc nên làm giảm các thao tác vào/ra liên quan đến quá trình học. Dữ liệu có thể được chuẩn hóa, đặc biệt khi sử dụng mạng neural hay phương pháp liên quan đến đo khoảng cách trong bước học. Chuẩn hóa bao hàm việc co dãn 12 tất cả giá trị của một thuộc tính rơi vào trong một khoảng nhỏ cụ thể, ví dụ như từ – 1 đến 1 hay từ 0 đến 1. 2.2.3. So sánh các phương pháp phân lớp Phương pháp phân lớp và dự báo có thể được so sánh và đánh giá dựa vào vào những tiêu chuẩn sau: Sự chính xác của dự báo: Liên quan đến khả năng dự đoán chính xác nhãn lớp mới hay dữ liệu trước đây chưa biết của mô hình. Tốc độ: Liên quan đến chi phí tính toán để tạo ra và sử dụng mô hình. Bền vững: Là khả năng của mô hình để dự đoán đúng một dữ liệu bị nhiễu hay bị mất giá trị. Khả cỡ: Liên quan đến năng lực để xây dựng một mô hình hiệu quả cho một dữ liệu có kích thước lớn. Tính có thể hiểu được: Liên quan đến mức độ nhận biết và hiểu được cung cấp bởi mô hình. 2.3. Khái niệm về bảng quyết định và cây quyết định 2.3.1. Bảng quyết định Bảng quyết định được định nghĩa hình thức là một cặp DS   U , A � d   trong đó U là tập hữu hạn, khác rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính điều kiện, d là thuộc tính quyết định. Với mọi u �U , a �A , ta ký hiệu giá trị thuộc tính a tại đối tượng u là a  u  . Nếu B   b1 , b2 ,..., bk  �A là một tập con các thuộc tính thì ta ký hiệu bộ các giá trị bi  u  bởi B  u  . Như vậy, nếu u và v là hai đối tượng, thì ta viết B  u   B  v  khi và chỉ khi bi  u   bi  v  với mọi i  1,..., k . Bảng 2.1 mô tả một tập dữ liệu đào tạo là bảng quyết định DS   U , C � d   với U   u1 ,..., u14  , A   a1 , a2 , a3 , a4  với a1 (Tuổi), a2 (Thu nhập), a3 (Sinh viên), a4 (Tỷ lệ tiền gửi) và thuộc tính quyết định d (Mua máy tính). U Tuổi Thu nhập Sinh viên Tỷ lệ tiền gửi Mua máy tính 13 <=30 Cao <=30 Sai Tốt Đú ng Cao Cao Sai Sai Tốt Rất tốt Sai Sai >40 Trung bình Sai Tốt Đúng >40 >40 31…40 Thấp Thấp Thấp Đúng Đúng Đúng Tốt Rất tốt Rất tốt Đúng Sai Đúng Thấp Đúng Tốt Đúng Trung bình Trung bình Trung bình Cao Trung bình Đúng Đúng Sai Đúng Sai Tốt Rất tốt Rất tốt Tốt Rất tốt Đúng Đúng Đúng Đúng Sai u1 u2 u4 3 1… 40 u3 u5 u6 Tru ng bìn hSa iTốt Sai u7 u9 < <=30 =30 u8 u10 u11 u12 u13 u14 >40 <=30 31…40 31…40 >40 Bảng 2.1 Bảng quyết định về dữ liệu đào tạo Xét bảng quyết định DS   U , A � d   . Mỗi tập con các thuộc tính P �A xác định một quan hệ hai ngôi trên U, ký hiệu là IND  P  , xác định bởi  IND  P  δu� , v  U U a P, a  u   a  v . 14 IND  P  là quan hệ tương đương vì thỏa mãn ba tính chất : phản xạ, đối xứng và bắc cầu. Nếu  u , v  �IND  P  thì hai đối tượng u và v tương đương nhau trên tập thuộc tính P. Quan hệ tương đương IND  P  xác định một phân hoạch trên U, ký hiệu là U / IND  P  hay U / P , mỗi thành phần trong U / P là một lớp tương đương. Xét tập thuộc tính P = {Thu nhập, Sinh viên} trong bảng quyết định ở Bảng 2.1, khi đó ta có phân hoạch: U / P    u1 , u2 , u3  ,  u4 , u8 , u12 , u14  ,  u5 , u6 , u7 , u9  ,  u10 , u11 ,  u13   Trong phân hoạch U / P , lớp tương đương  u1 , u2 , u3  có giá trị thuộc tính điều kiện là Thu nhập = ‘Cao’, Sinh viên = ‘Sai’ và hai giá trị thuộc tính quyết định là {Sai, Đúng}. Trong học máy, bảng quyết định được xem như là một tập dữ liệu mẫu có gán nhãn (thường là các mẫu huấn luyện hay mẫu học), các thuộc tính điều kiện gọi là các thuộc tính đầu vào, thuộc tính quyết định là thuộc tính nhãn, các giá trị thuộc tính quyết định là các nhãn hay nhãn phân lớp. Các đối tượng còn gọi là các mẫu, hay các ví dụ. 2.3.2. Cây quyết định Cây quyết định là một cấu trúc ra quyết định có dạng cây. Cây quyết định nhận đầu vào là một bộ giá trị thuộc tính mô tả một đối tượng hay một tình huống và trả về một giá trị rời rạc. Mỗi bộ thuộc tính đầu vào được gọi là một mẫu hay một ví dụ, đầu ra gọi là nhãn phân loại. Thuộc tính đầu vào còn được gọi là đặc trưng và có thể nhận giá trị rời rạc hoặc liên tục. Để cho đơn giản, trước tiên ta sẽ xem xét thuộc tính rời rạc, sau đó sẽ mở rộng cho trường hợp thuộc tính nhận giá trị liên tục. Trong cây quyết định, mỗi nút trung gian (tức là nút không phải nút lá) tương ứng với phép kiểm tra một thuộc tính. Mỗi nhánh phía dưới của nút đó tương ứng với một giá trị của thuộc tính hay một kết quả của phép thử. Khác với nút trung gian, nút lá không chứa thuộc tính mà chứa nhãn phân loại. Để xác định nhãn phân loại cho một ví dụ nào đó, ta cho ví dụ chuyển động từ gốc cây về phía nút lá. Tại mỗi nút, thuộc tính tương ứng với nút được kiểm tra, tùy theo giá trị của thuộc tính đó mà ví dụ được chuyển xuống nhánh tương ứng bên dưới. Quá trình này lặp lại cho đến khi ví dụ tới được nút lá và được nhận nhãn phân loại là nhãn của nút lá tương ứng. 15 Hình 2.2 mô tả một cây quyết định cho quyết định “Mua máy tính” từ bảng quyết định 2.1. Tuổi Tuổi <=30 31…40 Sinh Sinh viên viên sai không không > 40 Tỷ Tỷ lệ lệ tiền tiền gửi gửi có có đúng rất tốt có có không không Hình 2.2 một cây quyết định miêu tả khái niệm “mua máy tính” tốt có có 16 2.4. Thuật toán học cây quyết định Trước khi sử dụng cây quyết định, ta cần xây dựng cây quyết định hay “học” cây quyết định từ dữ liệu huấn luyện. Có nhiều thuật toán khác nhau được đề xuất và sử dụng để học cây quyết định từ dữ liệu, trong đó đa số dựa trên nguyên tắc chung là xây dựng cây theo kiểu tìm kiếm tham lam từ cây đơn giản tới cây phức tạp hơn. Phần này sẽ giới thiệu thuật toán học cây ID3, một thuật toán đơn giản nhưng có tính đại diện cho cách xây dựng cây như vậy. 2.4.1. Thuật toán ID3 học cây quyết định Trước khi sử dụng cây quyết định, ta cần xây dựng hay “học” cây quyết định từ dữ liệu huấn luyện. Có nhiều thuật toán khác nhau được đề xuất và sử dụng để học cây quyết định từ dữ liệu, trong đó đa số dựa trên nguyên tắc chung là xây dựng cây theo kiểu tìm kiếm tham lam từ cây đơn giản tới cây phức tạp hơn. Phần này sẽ giới thiệu thuật toán học cây ID3, một thuật toán đơn giản nhưng có tính đại diện cho cách xây dựng cây như vậy. Nhiệm vụ của thuật toán học là xây dựng cây quyết định phù hợp với tập dữ liệu huấn luyện, tức là cây quyết định có đầu ra giống (nhiều nhất) với nhãn phân loại cho trong tập mẫu. Trong trường hợp số thuộc tính nhỏ, việc xây dựng cây quyết định như vậy có thể thực hiện bằng cách liệt kê tất các cây quyết định hợp lệ và kiểm tra để chọn ra cây phù hợp với dữ liệu. Với số lượng thuộc tính lớn, số cây quyết định như vậy là rất lớn và không thể tìm kiếm theo kiểu vét cạn như vậy. Do đó, thuật toán học cây thường dựa trên nguyên tắc tham lam, xây dựng dần các nút từ trên xuống. Để bắt đầu, thuật toán học lựa chọn thuộc tính cho nút gốc. Thuộc tính được lựa chọn là thuộc tính cho phép phân chia tốt nhất các ví dụ thành những tập con, sao cho mỗi tập con càng đồng nhất càng tốt. Ở đây, đồng nhất được hiểu là các ví dụ có cùng nhãn phân loại. Sau khi lựa chọn được thuộc tính cho nút gốc, tập dữ liệu ban đầu sẽ được chia xuống các nhánh con do kết quả phép kiểm tra thuộc tính ở gốc. Với mỗi tập con dữ liệu, ta lại có một bài toán học cây dữ liệu mới và do vậy có thể lặp lại thủ tục ở trên với ít dữ liệu hơn và bớt đi một thuộc tính đã được sử dụng ở gốc. Quá trình xây dựng cây quyết định được lặp đệ quy như vậy cho tới khi xẩy ra những tình huống sau: 17  Sau khi phân chia tại một nút, tập dữ liệu con chỉ chứa các mẫu có cùng nhãn phân loại. Trong trường hợp này ta dừng quá trình phân chia ở đây, tạo một nút là và gán cho nút nhãn phân loại trùng với nhãn của các ví dụ tại nút đó.  Tất cả các thuộc tính đã được sử dụng ở phía trên, trong khi tập dữ liệu con còn chứa các nhãn phân loại khác nhau (ví dụ cả nhãn dương và nhãn âm). Đây là trường hợp các ví dụ có cùng giá trị thuộc tính nhưng lại khác nhãn phân loại và xẩy ra do dữ liệu huấn luyện có chứa nhiễu hoặc do các thuộc tính hiện có không cung cấp đủ thông tin để xác định đúng nhãn phân loại. Trong trường hợp này, thuật toán sẽ chọn nhãn chiếm đa số trong tập con để gán cho nút. Thuật toán học cây quyết định được mô tả như sau: 1) Khởi đầu: nút hiện thời là nút gốc chứa toàn bộ tập dữ liệu huấn luyện. 2) Tại nút hiện thời n, lựa chọn thuộc tính:  Chưa được sử dụng ở nút tổ tiên (tức là nút nằm trên đường đi từ gốc tới nút hiện thời)  Cho phép phân chia tập dữ liệu hiện thời thành các tập con một cách tốt nhất  Với mỗi giá trị thuộc tính được chọn thêm một nút con bên dưới  Chia các ví dụ ở nút hiên thời về các nút con theo giá trị thuộc tính được chọn 3) Lặp (đệ quy) cho tới khi:  Tất cả các thuộc tính đã được sử dụng ở các nút phía trên, hoặc  Tất cả ví dụ tại nút hiện thời có cùng nhãn phân loại  Nhãn của nút được lấy theo đa số nhãn của ví dụ tại nút hiện thời 2.4.2. Lựa chọn thuộc tính tốt nhất tại mỗi nút Điểm quan trọng nhất trong thuật toán xây dựng cây quyết định là lựa chọn thuộc tính tốt nhất tại mỗi nút. Trong trường hợp lý tưởng, thuộc tính lựa chọn là thuộc tính cho phép chia tập dữ liệu thành các tập con có cùng một nhãn, và do vậy chỉ cần một phép kiểm tra thuộc tính khi phân loại. Trong trường hợp nói chung, 18 thuộc tính lựa chọn cần cho phép tạo ta những tập con có độ đồng nhất cao nhất. Yêu cầu đặt ra là cần có cách đo độ đồng nhất của tập dữ liệu và mức tăng độ đồng nhất khi sử dụng một thuộc tính nào đó. Thuật toán xây dựng cây ID3 sử dụng độ đo entropy làm mức đo độ đồng nhất của tập dữ liệu. Trên cơ sở entropy, thuật toán tính độ tăng thông tin như mức tăng độ đồng nhất, từ đây xác định thuộc tính tốt nhất tại mỗi nút. Cho tập huấn luyện S , giả sử thuộc tính nhãn có m giá trị phân biệt định nghĩa m lớp khác nhau Ci với i  1,..., m . Entropy H  S  của thuộc tính nhãn để phân lớp tập dữ liệu S được tính bởi: m H ( S )   �pi log 2 ( pi ) (2.1) i 1 trong đó pi là xác suất để một mẫu tùy ý thuộc về lớp Ci và được tính bằng pi  Ci . Trong đó, Ci là số mẫu (lực lượng) của Ci và S là số mẫu (lực lượng) S của tập huấn luyện S. Ta thấy rằng entropy đạt giá trị nhỏ nhất bằng 0 nếu tất cả các mẫu trong S đều thuộc về cùng một lớp (thuần nhất), entropy đạt giá trị lớn nhất là 1 khi xác suất các nhãn bằng nhau. Như vậy, Entropy càng nhỏ thì tập đối tượng càng đồng nhất. Cho thuộc tính a có v giá trị khác nhau  a1 , a2 ,..., av  . Thuộc tính a có thể được sử dụng để chia S thành v lớp tương đương U /  a   S1 , S2 ,..., Sv  trong đó S j là mẫu mà thuộc tính a có giá trị a j . Nếu a được lựa chọn là thuộc tính thử (tức là thuộc tính tốt nhất tại nút phân chia), thì những lớp tương đương đó sẽ tương ứng với những nhánh đi ra từ nút a. Độ tăng thông tin (Information Gain), ký hiệu là IG, là chỉ số đánh giá độ tốt của thuộc tính trong việc phân chia tập dữ liệu thành những tập con đồng nhất. IG được tính dựa trên entropy theo công thức sau: v S j IG ( S , a )  H  S   � H ( S j ) j 1 S (2.2) 19 Trong đó, S j là số mẫu (lực lượng) của S j Ta sẽ phải tính toán độ tăng thông tin của từng thuộc tính, sau đó thuộc tính nào có độ tăng thông tin lớn nhất được chọn là thuộc tính thử cho tập S đã cho. Một nút được tạo ra và được gán nhãn bằng tên của thuộc tính, mỗi giá trị của thuộc tính sẽ tạo ra một nhánh. 2.4.3. Ví dụ minh họa Để trình bày ví dụ minh họa về thuật toán học cây quyết định, ta sẽ sử dụng bộ dữ liệu huấn luyện là bảng quyết định đã cho trong Bảng 2.1 về các bản ghi đào tạo được lấy từ cơ sở dữ liệu khách hàng. Thuộc tính nhãn (thuộc tính quyết định) là Mua máy tính, có hai giá trị phân biệt là Đúng và Sai, vì vậy có hai lớp phân biệt m = 2, C1 (Đúng), C2 (Sai). Có 14 mẫu trong bộ dữ liệu huấn luyện, trong đó có 9 mẫu thuộc lớp C1 và 5 mẫu thuộc lớp C2. U Thu nhập Sinh viên Tỷ lệ tiền gửi Cao Cao Sai Sai Tốt Rất tốt Mua máy tính Sai Sai >40 Trung bình Sai Tốt Đúng >40 >40 31…40 Thấp Thấp Thấp Đúng Đúng Đúng Tốt Rất tốt Rất tốt Đúng Sai Đúng Tuổi <=30 Cao <=30 Sai Tốt Đú ng u1 u2 u4 3 1… 40 u3 u5 u6 Tru ng bìn hSa iTốt Sai 20 u7 u9 < <=30 Thấp Đúng Tốt Đúng Trung bình Trung bình Trung bình Cao Trung bình Đúng Đúng Sai Đúng Sai Tốt Rất tốt Rất tốt Tốt Rất tốt Đúng Đúng Đúng Đúng Sai =30 u8 u10 u11 u12 u13 u14 >40 <=30 31…40 31…40 >40 Để tính toán lợi ích thông tin của mỗi thuộc tính, đầu tiên chúng ta phải sử dụng công thức 2.1 tính entropy H  S  để phân lớp một mẫu đã cho: H  S   9 9 5 5 log2  log2  0.940 14 14 14 14 Tiếp theo, chúng ta cần tính toán entropy của từng thuộc tính, giả sử bắt đầu với thuộc tính Tuổi. Chúng ta cần tìm nhìn vào phân bố của các mẫu đúng và sai cho mỗi giá trị của Tuổi. Chúng ta tính thông tin mong muốn cho từng phân bố ở trên 3 3 2 2 1) Với Tuổi = “30”: S1   u1 , u2 , u8 , u9 , u11  và H  S1    log2  log2 5 5 5 5 4 4 2) Với Tuổi=”31…40”: S2   u3 , u7 , u12 , u13  và H  S2    log 2  0 4 4 3 3 2 2 3) Với Tuổi=”>40”: S3   u4 , u5 , u6 , u10 , u14  và H  S3    log 2  log 2 5 5 5 5 Sử dụng công thức 2.2, độ tăng thông tin thu được với phân hoạch trên thuộc tính “Tuổi” sẽ là: 4 5 �5 � IG( S , Tuoi )  0.940  � H  S1   H  S2   H  S3  � 0.246 14 14 14 � � Tương tự, chúng ta có thể tính IG ( S , Thu nhap )  0.029 , IG ( S , Sinh vien )  0.151 và IG ( S , Ty le tien gui )  0.048 . Bởi Tuổi có độ tăng thông tin lớn nhất trong số các thuộc tính, nó có thể được lựa chọn là thuộc tính thử.