Showing posts with label Datamining. Show all posts
Showing posts with label Datamining. Show all posts

[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

in , , , , , /

[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)

[Algorithms] Cây quyết định với bài toán phân loại dữ liệu

in , , , , /

Cây quyết định với bài toán phân loại dữ liệu

Khái niệm cây quyết định

Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong (internal node) tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định. [Xem thêm...]

[Algorithms] Thuật toán K-Mean trong bài toán Phân cụm dữ liệu [VB]

in , , , , , , /

Thuật toán K-Mean trong bài toán Phân cụm dữ liệu


I. GIỚI THIỆU

Thuật toán K-means clustering do MacQueen giới thiệu trong tài liệu “J. Some Methods for Classification and Analysis of Multivariate Observations” năm 1967.
K-means Clustering là một thuật toán dùng trong các bài toán phân loại/nhóm n đối tượng thành k nhóm dựa trên đặc tính/thuộc tính của đối tượng (k £n nguyên, dương).
Về nguyên lý, có n đối tượng, mỗi đối tượng có m thuộc tính, ta phân chia được các đối tượng thành k nhóm dựa trên các thuộc tính của đối tượng bằng việc áp dụng thuật toán này.
Coi mỗi thuộc tính của đối tượng (đối tượng có m thuộc tính) như một toạ độ của không gian m chiều và biểu diễn đối tượng như một điểm của không gian m chiều. [Xem thêm...]

Thuật toán Cây quyết định C4.5 (slide - tổng quan)

in , , /

Thuật toán Cây quyết định C4.5 (slide - tổng quan)




Chúc các bạn thành công!

 


Subscribe to: Posts (Atom)