- ĐỀ TÀI: Tìm hiểu thuật toán ID3 trong xây dựng cây quyết định và khai thác bằng phần mềm WEKA để phân. - Tìm hiểu thuật toán ID3 trong xây dựng cây quyết định và khai thác bằng phần mềm WEKA để phân lớp dữ liệ u.. - Tổng quan về khai phá dữ liệu:. - Tại sao lại cần khai phá dữ liệu. - Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. - Người ta ước đoán rằng lượng thông tin trên to àn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. - Nói một cách hình ảnh là chúng ta đang “ngập” trong dữ liệu nhưng lại “đói” tri thức. - Câu hỏi đặt ra là liệu chúng ta có thể khai thác được gì từ những “núi” dữ liệu tưởng chừng như “bỏ đi” ấy không. - Khá nhiều định nghĩa về Data Mining và sẽ được đề cập ở phần sau, tuy nhiên có thể tạm hiểu rằng Data Mining như là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu được tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó.. - Khai phá dữ liệu là gì. - Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó.. - Các chức năng của khai phá dữ liệu:. - Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết.. - Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network), .v.v.. - Ứng dụng của khai phá dữ liệu. - Các kỹ thuật trong khai phá dữ liệu:. - Kỹ thuật phân tích phân loại (Classification Analysis). - Kỹ thuật khai phá dữ liệu đầu tiên là kỹ thuật phân tích phân loại. - Đây là kỹ thuật cho phép phân loại một đối tượng vào một hoặc một số lớp cho trước.. - Bạn có thể sử dụng kỹ thuật này để phân loại khách hàng, mặt hàng, v.v bằng cách mô tả nhiều thuộc tính để phân loại đối tượng vào một lớp cụ thể.. - Chúng ta thường sử dụng kỹ thuật khai thác dữ liệu này để lấy các thông tin quan trọng từ dữ liệu và siêu dữ liệu. - Vì vậy, trong phân tích phân loại, chúng ta cần áp dụng các thuật toán khác nhau tùy thuộc vào mục tiêu sử dụng.. - Hay các doanh nghiệp có thể áp dụng kỹ thuật này để phân loại khách hàng theo đối tượng hay độ tuổi.. - Kỹ thuật Association Rule Learning. - Kỹ thuật Association Rule Learning trong khai phá dữ liệu được sử dụng để xác định mối quan hệ giữa các biến khác nhau trong cơ sở dữ liệu. - Ngoài ra, nó còn được sử dụng để “giải nén” các mẫu ẩn trong dữ liệu. - Thêm vào đó, các doanh nghiệp sử dụng kỹ thuật này để xác định hành vi mua sắm, phân tích dữ liệu trong giỏ hàng của khách hàng tiềm năng. - Trong lĩnh vực Công nghệ Thông tin, các lập trình viên sử dụng kỹ thuật này để xây dựng các chương trình Machine Learning.. - Kỹ thuật phát hiện bất thường (Anomaly or Outlier Detection):. - Về cơ bản, kỹ thuật khai phá dữ liệu (Data Mining) này dùng để nhấn mạnh vào việc quan sát các mục dữ liệu trong bộ dữ liệu để tìm ra các tập dữ liệu không khớp. - Bất thường ở đây có thể đề cập đến độ lệch, sự khác thường, các nhiễu và ngoại lệ.. - Sự bất thường được xem là khá quan trọng vì nó có thể cung cấp một số thông tin cần thiết. - Nó có thể là một dữ liệu khác biệt so với mức trung bình chung trong một tập dữ liệu. - Điều này chỉ ra rằng một cái gì đó khác thường đã xảy ra và các nhà phân tích dữ liệu cần chú ý.. - Kỹ thuật này có thể được sử dụng trong nhiều lĩnh vực khác nhau. - Kỹ thuật phân tích theo cụm (Clustering Analysis):. - “Cụm” có nghĩa là một nhóm các đối tượng dữ liệu. - Về cơ bản, kỹ thuật khai phá dữ liệu này thường được ứng dụng để tạo hồ sơ khách hàng. - Kỹ thuật phân tích hồi quy (regression analysis):. - Theo thuật ngữ thống kê, phân tích hồi quy được sử dụng để xác định và phân tích mối quan hệ giữa các biến. - Kỹ thuật dự báo (prediction):. - Trong khai phá dữ liệu, kỹ thuật dự báo được ứng dụng ở một số trường hợp đặc biệt. - Chẳng hạn, bạn có thể sử dụng kỹ thuật dự báo cho việc bán hàng để dự đoán lợi nhuận cho tương lai. - Giả sử, bán hàng là một biến độc lập, lợi nhuận có thể là một biến phụ thuộc. - Khi đó, chúng ta có thể vẽ đường cong hồi quy để dự đoán lợi nhuận.. - Cây quyết định. - Khái niệm Cây quyết định (Decision Tree). - Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc được dùng để phân lớp các đối tượng dựa vào dãy các luật. - Các thuộc tính của đối tượngncó thể thuộc các kiểu dữ liệu khác nhau như Nhị phân (Binary. - Định danh (Nominal), Thứ tự (Ordinal), Số lượng (Quantitative) trong khi đó thuộc tính phân lớp phải có kiểu dữ liệu là Binary hoặc Ordinal.. - Tóm lại, cho dữ liệu về các đối tượng gồm các thuộc tính cùng với lớp (classes) của nó, cây quyết định sẽ sinh ra các luật để dự đoán lớp của các dữ liệu chưa biết.. - Ta hãy xét một ví dụ 1 kinh điển khác về cây quyết định. - Giả sử dựa theo thời tiết mà các bạn nam sẽ quyết định đi đá bóng hay không?. - Dựa vào những thông tin trên, bạn có thể xây dựng được mô hình như sau:. - Mô hình cây quyết định. - Entropy trong Cây quyết định (Decision Tree). - Với một phân phối xác suất của một biến rời rạc x có thể nhận n giá trị khác nhau x 1 ,x 2 ,…,x n. - Ta có thể thấy rằng, Entropy đạt tối đa khi xác suất xảy ra của hai lớp bằng nhau.. - Information Gain dựa trên sự giảm của hàm Entropy khi tập dữ liệu được phân chia trên một thuộc tính. - Để xây dựng một cây quyết định, ta phải tìm tất cả thuộc tính trả về Infomation gain cao nhất.. - Để xác định các nút trong mô hình cây quyết định, ta thực hiện tính Infomation Gain tại mỗi nút theo trình tự sau:. - •Bước 2: Tính hàm số Entropy tại mỗi thuộc tính: với thuộc tính x, các điểm dữ liệu trong S được chia ra K child node S 1 , S 2. - 0.63 Ta có thể tính hệ số Information Gain như sau:. - Thuật toán C4.5. - Trong thuật toán ID3, Information Gain được sử dụng làm độ đo. - Do vậy, để khắc phục nhược điểm trên, ta sử dụng độ đo Gain Ratio (trong thuật toán C4.5) như sau:. - Khi đó, cây có thể sẽ rất phức tạp (nhiều node) với nhiều leaf node chỉ có một vài điểm dữ liệu. - Để tránh trường họp này, ta có thể dừng cây theo một số phương pháp sau đây:. - Class cho leaf node này có thể được xác. - Thuật toán CHAID: tạo cây quyết định bằng cách sử dụng thống kê chi - square để xác định các. - Các biến mục tiêu đầu vào có thể là số (liên tục) hoặc phân loại.. - Thuật toán C&R: sử dụng phân vùng đệ quy để chia cây. - Tham biến mục tiêu có thể dạng số. - Ưu/nhược điểm của thuật toán cây quyết định. - Cây quyết định là một thuật toán đơn giản và phổ biến. - Thuật toán này được sử dụng rộng rãi bới những lợi ích của nó:. - Dữ liệu đầu vào có thể là là dữ liệu missing, không cần chuẩn hóa hoặc tạo biến giả. - Có thể làm việc với cả dữ liệu số và dữ liệu phân loại. - Có thể xác thực mô hình bằng cách sử dụng các kiểm tra thống kê Có khả năng là việc với dữ liệu lớn. - Kèm với đó, cây quyết định cũng có những nhược điểm cụ thể:. - Mô hình cây quyết định phụ thuộc rất lớn vào dữ liệu của bạn. - nhỏ trong bộ dữ liệu, cấu trúc mô hình cây quyết định có thể thay đổi hoàn toàn.. - Cây quyết định hay gặp vấn đề overfitting. - Thuật toán ID3:. - ID3 là một giải thuật hay vì cách biểu diễn tri thức học được của nó, tiếp cận của nó trong việc quản lý tính phức tạp, heuristic của nó dùng cho việc chọn lựa các khái niệm ứng viên, và tiềm năng của nó đối với việc xử lý dữ liệu nhiễu.. - Biểu diễn này cho phép chúng ta xác định phân loại của một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó.. - Như vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ rèn luyện (training example) hay còn gọi là dữ liệu rèn luyện (training data).. - Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó.. - Output: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chưa gặp trong tương lai.. - Giải thuật ID3 xây dựng cây quyết định được trình bày như sau:. - Chọn A <= thuộc tính quyết định “tốt nhất” cho nút kế tiếp 2. - Gán A là thuộc tính quyết định cho nút. - Độ lợi thông tin thuộc tính Humidity:. - Độ lợi thông tin của thuộc tính Outlook:. - Chọn thuộc tính:. - Phân nhánh bằng thuộc tính nhị phân:. - Biến đổi cây quyết định thành luật:. - đầu tiên tạo bảng dữ liệu bằng excel như sau:. - tại phần bên trái ở mục result list click chuột phải vào “trees.j48” chọn visualize trees phần mềm sẽ hiện cây quyết định. - T ương t ự như bài toán golf trên , ta c ũng l ưu dữ liệu dưới dạng .cs v , m ở trong phầ n m ềm weka ,tuy nhiên STT không ph ải l à thu ộc t ính d ữ liệu n ên ở tab preprocess ta đ ánh tick vào ô STT r ồi ấn remove n ó đi
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt