Công Thức Tính Entropy ở Trên Là Công Thức Tổng Quát đối Với Trường ...

1. Trang chủ >
2. Công nghệ thông tin >
3. Hệ thống thông tin >

Công thức tính entropy ở trên là công thức tổng quát đối với trường hợp S có m lớp. Trong

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (878.31 KB, 29 trang )

Phân hoạch S theo thuộc tính APhân hoạch S theo thuộc tính A’2.1.1. Information GainĐộ đo Information Gain được đưa ra để giúp việc lựa chọn thuộc tính phân tách. Độđo này được sử dụng trong thuật toán ID3. Mỗi thuộc tính điều kiện sẽ phân tách quần thể Sthành các phân hoạch. Information Gain sử dụng đại lượng entropy của lý thuyết thông tin đểcho biết mức độ trùng lắp giữa các phân hoạch được tạo ra, nghĩa là một phân hoạch sẽ chứacác phần tử từ một lớp hay từ nhiều lớp khác nhau.Thuộc tính A phân hoạch S thành v phân hoạch được ký hiệu như sau {SA1, SA2 ,…, SAv}.Với v là tập giá trị của A. Công thức tính Information Gain:Với Entropy (SAj) là mức độ hỗn loạn của các phân hoạch SAj do thuộc tính A tạo ra.Chọn thuộc tính Aj nào có Gain(S,Aj) LỚN NHẤT làm thuộc tính phân táchNhận xét: Do Entropy(S) là hằng số đối với tất cả thuộc tính, mức độ hỗn loạn của các phânAhoạch do thuộc tính Aj tạo ra (Entropy (S ))đượcj mong đợi là có giá trị càng nhỏ càng tốt (íthỗn loạn). Do đó kết quả sẽ là chọn Gain (S,Aj) của thuộc tính Aj nào có giá trị lớn nhất.Ví dụ 2: Có tập dữ liệu Play Tennis như sau:Xét thuộc tính Outlook: Outlook có 3 giá trị “Sunny”, “Overcast”, và “Rain”. Do đóthuộc tính Outlook tạo ra 3 phân hoạch. Lần lượt tính Entropy cho mỗi phân hoạch theo côngthức tính Entropy phần 2.1 ta được:Theo công thức tính Gain (S, Outlook):phân tách. Tương tự, lần lượt tính được Gain cho các thuộc tính khác:Gain (S,Humidity)=0.151, Gain (S,Wind)=0.048, Gain (S,Temp)=0.029Thuộc tính Outlook có Gain(S,Outlook) cao nhất nên chọn Outlook làm thuộc tínhVí dụ 3: giả sử cũng tập dữ liệu Play Tennis như Ví dụ 2 nhưng có bổ sungthêm một thuộc tính When (thời gian chơi Tennis) như sau:Gain(S,When) = 0.940 – (4/14)*1 – (3/14)*0.918 – (3/14)*0.918 = 0.261Nhận xét: bây giờ do thuộc tính When có Gain (S,When) cao nhất 0.261 (lớn hơnGain(S,Outlook)=0.246 đã tính ở Ví dụ 2), nên sẽ chọn thuộc tính When làm thuộc tính phântách thay vì là thuộc tính Outlook. Tuy nhiên, theo quan sát thì do thuộc tính When có nhiều giátrị (5 giá trị) hơn thuộc tính Outlook (3 giá trị), trong đó có một phân hoạch là When=7pm chỉ có1 phần tử, nên entropy của mỗi phân hoạch do thuộc tính When tạo ra thấp, từ đó dẫn đến Gain(S, When) cao.Như vậy với độ đo Information Gain có xu hướng “thiên vị” cho thuộc tính nhiềugiá trị (cây có nhiều nhánh). Điều này làm ảnh hưởng đến kết quả dự đoán. Do đó cần một độ đocải tiến hơn để giải quyết vấn đề này.2.1.2. Gain RatioĐộ đo Gain Ratio được đặt ra để giải quyết vấn đề một thuộc tính tạo ra rất nhiềuphân hoạch nhưng có thể mỗi phân hoạch chỉ gồm 1 phần tử. Độ đo này được sử dụng trongthuật toán C4.5 và đã chuẩn hóa đươc Information Gain nhờ vào Split Information (thông tinphân tách). [1] Công thức tính Split Information như sau:Nhậnxét:Thôngtin phân tách này có ý nghĩa: nếu thuộc tính A có càng nhiều giá trịthì thông tin phân tách của nó (SplitInfo (S,A)) càng lớn. Khi đó lấy Gain(S,A) chia choSplitInfo(S,A) để có được độ đo GainRation (S, A) như công thức:Chọnthuộc tính Aj nào có GainRatio(S, Aj) LỚN NHẤT làm thuộc tính phân tách.Độ đo Gain Ratio đã giải quyết được xu hướng “thiên vị” cho thuộc tính nhiều giátrị của độ đo Information Gain vì giả sử hai thuộc tính A và B có cùng Gain(Gain(A)=Gain(B)). Nhưng nếu thuộc tính A có nhiều giá trị hơn thuộc tính B, khi đó SplitInfocủa A sẽ lớn hơn SplitInfo của B. Do đó theo công thức, giá trị Gain Ratio của B sẽ lớn hơnGain Ratio của A, và cuối cùng sẽ chọn B làm thuộc tính phân tách. Như vậy Gain Ratio đãchuẩn hóa được trường hợp thiên vị cho thuộc tính nhiều giá trị của Information Gain trước đó.Ví dụ 4: Tương tự bài toán ở Ví dụ 3 đã trình bày ở trên, tính lại GainRatio chothuộc tính Outlook và WhenSplitInfo(S ,When)Thuật toán C4.53.1. Giới thiệu C4.5Với những đặc điểm C4.5 là thuật toán phân lớp dữ liệu dựa trên cây quyết định hiệu quảvà phổ biến trong những ứng dụng khai phá cơ sở dữ liệu có kích thước nhỏ. C4.5 sử dụng cơchế lưu trữ dữ liệu thường trú trong bộ nhớ, chính đặc điểm này làm C4.5 chỉ thích hợp vớinhững cơ sở dữ liệu nhỏ, và cơ chế sắp xếp lại dữ liệu tại mỗi node trong quá trình phát triển câyquyết định. C4.5 còn chứa một kỹ thuật cho phép biểu diễn lại cây quyết định dưới dạng mộtdanh sách sắp thứ tự các luật if-then (một dạng quy tắc phân lớp dễ hiểu). Kỹ thuật này cho phéplàm giảm bớt kích thước tập luật và đơn giản hóa các luật mà độ chính xác so với nhánh tươngứng cây quyết định là tương đương.Tư tưởng phát triển cây quyết định của C4.5 là phương pháp HUNT đã nghiên cứu ở trên.Chiến lược phát triển theo độ sâu (depth-first strategy) được áp dụng cho C4.5.3.2. Các độ đo sử dụng trong C4.5Phần lớn các hệ thống học máy đều cố gắng để tạo ra 1 cây càng nhỏ càng tốt, vì nhữngcây nhỏ hơn thì dễ hiểu hơn và dễ đạt được độ chính xác dự đoán cao hơn.Do không thể đảm bảo được sự cực tiểu của cây quyết định, C4.5 dựa vào nghiên cứu tốiưu hóa, và sự lựa chọn cách phân chia mà có độ đo lựa chọn thuộc tính đạt giá trị cực đại.Hai độ đo được sử dụng trong C4.5 là information gain và gain ratio.3.2.1. Information GainTrong đó: Value(A) là tập các giá trị của thuộc tính A, Sv là tập con của S mà A nhận giá trị vVí dụ mô tả cách tính information gainXét CSDL sau:0.048InfoGain(W) = 0.029Suy ra: Ta sẽ chọn Outlook vì có InfoGain lớn nhấtXétthuộctínhOutlook(O)XtínT Tính InfoGain cho từng nhánh (chưa được phân lớp) để tăng trưởng cây (một cách đệ(T)Quy)TƣIn

Xem Thêm

Tài liệu liên quan

• Tiểu luận môn khai phá dữ liệu MÔ HÌNH CÂY QUYẾT ĐỊNH THUẬT TOÁN C4.5
  • 29
  • 1,652
  • 12
• 24 ke sach trong thuong truong
  • 4
  • 0
  • 0
• ky nang cua nguoi thanh cong
  • 25
  • 0
  • 0
• Kế toán bán hàng và xác định kết quả kinh doanh tại cửa hàng xăng dầu hưng lợi
  • 48
  • 1
  • 11
• Cung cấp một số dịch vụ cho các đối tác của VIB trên Internet
  • 123
  • 101
  • 0

Tải bản đầy đủ (.docx) (29 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(977.74 KB) - Tiểu luận môn khai phá dữ liệu MÔ HÌNH CÂY QUYẾT ĐỊNH THUẬT TOÁN C4.5-29 (trang) Tải bản đầy đủ ngay ×