[Thuật toán Cây quyết định] Chương trình mô phỏng thuật toán ID3 – Cây Quyết Định

[Thuật toán Cây quyết định] Chương trình mô phỏng thuật toán ID3 – Cây Quyết Định

>> Hướng dẫn lập trình C#

1. Giải thuật ID3:

ID3_algorithm(Training_Set, Class_Labels, Attributes)

Tạo nút Root của cây quyết định

   If tất cả các ví dụ của Training_Set thuộc cùng lớp c

   Return Cây quyết định có nút Root được gắn với (có nhãn) lớp c

   If Tập thuộc tính Attributes là rỗng

   Return Cây quyết định có nút Root được gắn với nhãn lớp ≡ Majority_Class_Label(Training Set)

   A ← Thuộc tính trong tập Attributes có khả năng phân loại “tốt nhất” đối với Training_Set

   Thuộc tính kiểm tra cho nút Root ← A

   For each Giá trị có thể v của thuộc tính A

 Bổ sung một nhánh cây mới dưới nút Root, tương ứng với trường hợp: “Giá trị của A là v”

   Xác định Training_Setv = {ví dụ x | x ⊆ Training_Set, xA=v}

  If (Training_Setv là rỗng) Then

  Tạo một nút lá với nhãn lớp ≡ Majority_Class_Label(Training_Set)

Gắn nút lá này vào nhánh cây mới vừa tạo

Else Gắn vào nhánh cây mới vừa tạo một cây con sinh ra bởi ID3_algorithm(Training_Setv, Class_Labels, {Attributes A})

Return Root


2. Giao diện chính của chương trình Demo gồm 4 phần:

o Phần 1: Bảng lưu dữ liệu training (Data Training).

o Phần 2: Ghi ra các bước giải của thuật toán (Solutions).

o Phần 3: Vẽ cây minh họa cho thuật toán (Decision Tree).

o Phần 4: Các chức năng của chương trình (Control).


Có 4 button với các chức năng như sau:

- Load Data: Đưa dữ liệu training vào chương trình.

- ID3 – Alg: Chạy giải thuật ID3.

- Reset: Khởi động, chạy lại chương trình.

- About: Thông tin về chương trình.


3.  Các bước chạy chương trình:

- Đầu tiên, nạp dữ liệu vào chương trình bằng button Load Data.

Dữ liệu được đưa lên bảng Data Training (Phần 1).

- Sau đó, nhấn button ID3 – Alg để chạy giải thuật.

Các bước giải sẽ được hiện ra ở phần 2 (Solutions).

Cây được vẽ ra ở phần 3 (Decision Tree).


4. Giao diện chương trình:


Chương trình gồm những hàm chính sau:

 Hàm tính Entropy:

· Công thức:    Entropy (S) = – p+ log2 p+ – p- log2 p-

· Code [C#]:

private double GetEntropy(int Positives , int Negatives)
{
if (Positives == 0)
return 0;
if (Negatives == 0)
return 0;
double Entropy;
int total = Negatives + Positives;
double RatePositves = (double)Positives / total;
double RateNegatives = (double)Negatives / total;
Entropy = -RatePositves * Math.Log(RatePositves, 2) – RateNegatives * Math.Log(RateNegatives, 2);
return Entropy;
}


 Hàm tính Gain:

· Công thức:


· Code [C#]:

private double Gain(List<List<string>> Examples, Attribute A, string bestat)
{
double result;
int CountPositives = 0;
int[] CountPositivesA = new int[A.Value.Count];
int[] CountNegativeA = new int[A.Value.Count];
int Col = Attributes.IndexOf(A);
for (int i = 0; i < A.Value.Count; i++)
{
CountPositivesA[i] = 0;
CountNegativeA[i] = 0;
}
for (int i = 0; i < Examples.Count; i++)
{
int j = A.Value.IndexOf(Examples[i][Col].ToString());
if (Examples[i][Examples[0].Count – 1]==”yes”)
{
CountPositives++;
CountPositivesA[j]++;
}
else
{
CountNegativeA[j]++;
}
}
result = GetEntropy(CountPositives, Examples.Count – CountPositives);
for (int i = 0; i < A.Value.Count; i++)
{
double RateValue = (double)(CountPositivesA[i] + CountNegativeA[i]) / Examples.Count;
result = result – RateValue * GetEntropy(CountPositivesA[i], CountNegativeA[i]);
}
Solution = Solution + “n * Gain(” + bestat + “,” + A.Name + “) = ” + result.ToString();
return result;
}



 Hàm chọn đặc tính tốt nhất:

· Phương pháp:
    - Dựa vào giá trị gain của các đặc tính, đặc tính nào có Gain lớn nhất.

    - Chọn đặc tính đó – đặc tính tốt nhất.

· Code [C#]:

private Attribute GetBestAttribute(List<List<string>> Examples, List<Attribute> Attributes, string bestat)
{
double MaxGain = Gain(Examples, Attributes[0], bestat);
int Max = 0;
for (int i = 1; i < Attributes.Count; i++)
{
double GainCurrent = Gain(Examples, Attributes[i], bestat);
if (MaxGain < GainCurrent)
{
MaxGain = GainCurrent;
Max = i;
}
}
return Attributes[Max];
}
 Hàm thực hiện giải thuật ID3:
Code:
private TreeNode ID3(List<List<string>> Examples, List<Attribute> Attribute,string bestat)
{
if (CheckAllPositive(Examples))
{
return new TreeNode(new Attribute(“Yes”));
}
if (CheckAllNegative(Examples))
{
return new TreeNode(new Attribute(“No”));
}
if (Attribute.Count == 0)
{
return new TreeNode(new Attribute(GetMostCommonValue(Examples)));
}
Attribute BestAttribute = GetBestAttribute(Examples, Attribute, bestat);
int LocationBA = Attributes.IndexOf(BestAttribute);
TreeNode Root = new TreeNode(BestAttribute);
for (int i = 0; i < BestAttribute.Value.Count; i++)
{
List<List<string>> Examplesvi = new List<List<string>>();
for (int j = 0; j < Examples.Count; j++)
{
if (Examples[j][LocationBA].ToString() == BestAttribute.Value[i].ToString())
Examplesvi.Add(Examples[j]);
}
if (Examplesvi.Count==0)
{
return new TreeNode(new Attribute(GetMostCommonValue(Examplesvi)));
}
else
{
Attribute.Remove(BestAttribute);
Root.AddNode(ID3(Examplesvi, Attribute,BestAttribute.Value[i]));
}
}
return Root;
}


(theo csshare)

Quảng cáo

Загрузка...

Categories

8051 (1) AI (1) AI programming (1) amazon (1) Android (27) ASP (1) Assembly (17) Bài giảng (2) Bài giảng lập trình C và Cpp (16) bài giảng quản lý dự án CNTT (1) bài tập java (1) bài tập lập trình (1) Bài viết hay (62) Bản đồ tư duy (1) Bidvertiser (1) Biểu diễn thuật toán (1) bitcoin (1) blockchain (1) Blockchain là gì (1) Bubble-Sort (1) C (77) C Plus Plus (103) C sharp (11) C++ (3) cấu trúc dữ liệu giải thuật (1) Cây (tree) (2) Cây quyết định (3) CDSL phân tán (1) Chữa bài tập Java (1) code assembly (1) Công nghệ điện toán đám mây (1) Công nghệ lập trình (1) Cơ sở dữ liệu (10) CSS (2) Cuộc cách mạng công nghiệp 4.0 (1) Danh ngôn lập trình (1) Danh sách liên kết (list) (1) Datamining (4) Đại số gia tử và ứng dụng (1) đăng ký Amazon (1) Đăng ký hosting (2) đặt hàng trên Amazon (1) Đệ quy (2) Đồ họa (4) Độ phức tạp của thuật toán (1) ebook-csdl (1) ebook-giaithuat (1) ebook-laptrinh (1) ebook-phancung-mang (1) ebook-tinhocungdung (1) ebook-web (1) Exceptions (1) Genetic Algorithm (1) Giải hệ phương trình tuyến tính (5) giải thuật (3) giải thuật Đệ quy (1) Giáo trình (2) Góc học tập (34) Góc suy ngẫm (1) Google App Engine (2) Heap-Sort (1) Hệ quản trị CSDL (1) Học lập trình (125) Học lập trình C và CPP qua ví dụ (15) học lập trình Java (7) HostGator (1) hợp ngữ (1) HPH (25) HTML (1) Hướng Dẫn Đăng Ký Tên Miền và Host Trên Hostgator (1) hướng dẫn mua host (1) hướng dẫn nhận tiền (1) hướng dẫn payoneer (1) Hướng dẫn sử dụng Emu8086 (1) hướng dẫn viết báo (1) hướng đăng ký tên miền (1) Insert-sort (2) iOS (1) Java (50) Java Căn bản (5) java core (3) Java GUI (1) JavaScript (3) Kiếm tiền online (10) Kỹ thuật đồ họa máy tính (9) Kỹ thuật lập trình (16) kỹ thuật SEO (1) Lập trình 8051 với C/C++ (1) Lập trình căn bản (7) Lập trình Cơ sở dữ liệu (2) Lập trình điều khiển thiết bị (1) Lập trình hợp ngữ (1) Lập trình hướng đối tượng (38) Lập trình hướng đối tượng với Java (6) Lập trình mạng (6) Lập trình mobile (3) Lập trình nhúng (1) Lập trình trí tuệ nhân tạo (1) lập trình vi xử lý (1) lập trình viên (1) Lập trình viên độc lập (1) Luyện thi IC3 (4) Lý thuyết Cơ sở dữ liệu (2) Lý thuyết đồ thị (11) Mạng máy tính (1) Mẹo tìm kiếm trên Google (1) Merge-Sort (1) MS Access (1) Mua hàng trên Amazon (1) Nghiên cứu khoa học (1) ngon-ngu-khac (1) Ngôn ngữ lập trình (1) Nhúng code Assembly trong C\C++ (2) Những lỗi thường gặp khi lập trình (1) Oracle (1) Pascal (3) payoneer (1) people-group (1) phần cứng máy tính (1) PHP (1) Quản lý dự án CNTT (1) Queue (hàng đợi) (1) Quick-Sort (1) Seclection-sort (2) SEO (1) SQL (5) Stack (ngăn xếp) (1) Swift (8) tài liệu CNTT miễn phí (2) Tài liệu tham khảo (2) thanh toán quốc tế (1) Thiết kế Web (2) Thủ thuật máy tính (5) thuattoan-khac (1) Thuật toán (41) Thuật toán di truyền (2) Thuật toán Đệ quy (4) Thuật toán K-Mean (1) Thuật toán khác (9) Thuật toán leo đồi (1) Thuật toán ma trận (7) Thuật toán Sắp Xếp -Sort (9) Thuật toán Tìm kiếm - Search (5) Thương mại điện tử (4) Tiện ích máy tính (3) Tìm hiểu Blockchain (1) Tìm kiếm nhị phân (2) Tìm kiếm tuần tự (Line search) (2) Tin học văn phòng (5) Tin tức công nghệ (7) Tính định thức của ma trận (1) Toán rời rạc (12) Trí tuệ nhân tạo (8) Tự học lập trình Android (14) Tự học lập trình C và CPP (14) tự học lập trình iOS (8) Tự học lập trình java qua các ví dụ (7) Ứng dụng cơ sở dữ liệu (1) VB (2) vẽ ngôi nhà (1) ví dụ Assembly (1) xcode (8) XML (1) Xử lý ma trận (mảng 2 chiều) (7) Xử lý mảng 1 chiều (1) Xử lý ngoại lệ (1)