Cài đặt Thuật giải Cây ID3

woa.. thế là gần 1 tuần mất ăn mất ngủ, không đi chơi tết (hix).. mình đã cài xong thuật giải ID3, nhưng mới chỉ là 1 số bước đầu minh họa cho các ví dụ thôi. Với 1 ví dụ nhỏ thì thuật giải chạy good, nhưng mình chưa thử với 1 lượng dữ liệu lớn. Nhất là mình demo bằng tay, chứ chưa kết hợp lưu trữ dữ liệu trên sql (hix, mới bước đầu thôi mà. Chặng tới còn gian nan lém)

Dưới đây là code của cây ID3, hẳn nhiên mình chỉ đưa code chính, còn các code nhỏ thì mọi ng xem rồi tự viết nha, hoặc là mình sẽ đưa sau. Vì chủ yếu là mình đưa code minh họa thuật giải ID3, chứ mình không đưa nguyên bài.

Có phần cũng chưa hay lắm, là mình dùng độ entropy. Thực tế hum trước nhóm mình đã thảo luận là sẽ dùng gini. Thực ra, mình cũng chưa test kĩ vấn đề này, nên tạm thời dùng chuẩn enropy đã, sau đó rồi đổi sang gini sau.

Code (hàm chính)

private TreeNode CayCon(DataTable dulieu, string thuoctinhMuctieu, 
            Attribute[] thuoctinh)
{
   if (dulieuYes(dulieu, thuoctinhMuctieu) == true)
        return new TreeNode(new Attribute(true));

   if (dulieuNo(dulieu, thuoctinhMuctieu) == true)
         return new TreeNode(new Attribute(false));

   if (thuoctinh.Length == 0)
       return new TreeNode(new Attribute(LayGTThongThuong(dulieu, 
             thuoctinhMuctieu)));

    mTong = dulieu.Rows.Count;
    mThuocTinhMucTieu = thuoctinhMuctieu;
    mTongTichCuc = TinhTongTichCuc(dulieu);

   mEntropy = TinhEntropy(mTongTichCuc, mTong - mTongTichCuc);

   Attribute ttTotnhat = ThuoctinhTotNhat(dulieu, thuoctinh);

   TreeNode goc = new TreeNode(ttTotnhat);

   DataTable dlieu = dulieu.Clone();

   foreach (string gtri in ttTotnhat.giatri)
    {
       dlieu.Rows.Clear();

       DataRow[] dg = dulieu.Select(ttTotnhat.TenThuocTinh + " = " 
           + "'" + gtri + "'");

       foreach (DataRow r in dg)
        {
           dlieu.Rows.Add(r.ItemArray);
        }
        ArrayList mthuoctinh = new ArrayList(thuoctinh.Length - 1);
        for (int i = 0; i < thuoctinh.Length; i++)
        {
            if (thuoctinh[i].TenThuocTinh != ttTotnhat.TenThuocTinh)
                mthuoctinh.Add(thuoctinh[i]);
        }

        if (dlieu.Rows.Count == 0)
        {
            return new TreeNode(new Attribute(LayGTThongThuong(dlieu, 
                thuoctinhMuctieu)));
        }
        else
        {
            TreeID3 tId3 = new TreeID3();
            TreeNode NodeCon = tId3.GanCay(dlieu, thuoctinhMuctieu, 
                (Attribute[])mthuoctinh.ToArray(typeof(Attribute)));
                goc.AddTreeNode(NodeCon, gtri);
        }
    }
    return goc;
}

public TreeNode GanCay(DataTable dulieu, string thuoctinhMuctieu, 
    Attribute[] thuoctinh)
{
    mDuLieu = dulieu;
    return CayCon(mDuLieu, thuoctinhMuctieu, thuoctinh);
}

ngoài ra, còn có thêm các hàm hỗ trợ sau:

public class Attribute
{
       public Attribute(string ten, string[] giatri)
       public Attribute(object nhan)
       public string TenThuocTinh
        public string[] giatri
        public bool GiaTriHopLe(string gtri)
        public int GiaTriHienTai(string gtri)
        public override string ToString()
}

public class TreeNode
{
        public TreeNode(Attribute thuoctinh)
        public void AddTreeNode(TreeNode tn,
            string tengiatri)
        public int TongNodeCon
        public TreeNode LayCon(int hientai)
        public Attribute thuoctinh
        public TreeNode LayNhanhCon(string nhanhCon)
}

public class TreeID3
{
        private int TinhTongTichCuc(DataTable dulieu)
        private double TinhEntropy(int yes, int no)
        private void LayGiaTriThuocTinh(DataTable dulieu, Attribute thuoctinh, 
            string gtri, out int yes, out int no)
        private double GTDatDuoc(DataTable dulieu, 
             Attribute thuoctinh)
        private Attribute ThuoctinhTotNhat(DataTable dulieu, 
              Attribute[] ttinh)
        private bool dulieuYes(DataTable dulieu, string thuoctinhMuctieu)
        private bool dulieuNo(DataTable dulieu, string thuoctinhMuctieu)
        private ArrayList DulieuKhacBiet(DataTable dulieu, 
               string thuoctinhMuctieu)
        private object LayGTThongThuong(DataTable dulieu, 
               string thuoctinhMuctieu)
}

Đây là bản debug, mọi người xem thử nha. với bộ test dữ liệu Đi Bơi là:

bầu trời, nhiệt độ, độ ẩm, gió, kết quả

nắng, cao, cao, không, có
nắng, cao, cao, có, không
mây, cao, cao, không, có
mưa, cao, cao, không, có
mưa, thấp, bình thường, không, có
mưa, thấp, bình thường, có, không
mây, thấp, bình thường, có, có
nắng, trung bình, cao, không, không
nắng, thấp, bình thường, không, có
mưa, trung bình, bình thường, không, có
nắng, trung bình, bình thường, không, có
mây, trung bình, cao, có, không
mây, cao, bình thường, không, có
mưa, trung bình, cao, có, không

và đây là bản debug:
http://www.mediafire.com/?iamqyzmtklt
nó chỉ có tác dụng tham khảo thôi ^^

khi tính entropy, duyệt dữ liệu như vậy là rất dở, nên chuyển sang dang truy vấn để tính, những gì liên quan đến dữ liệu thì để cho SQL làm.

Ban oi minh dang co bai tap tim hieu ve thuat toan nay. Minh rat mong duoc su giup do cua cac ban. Neu co the ban gui code thuat toan ID3 ve cho minh theo dia chi huyentrangcntt@gmail.com cam on ban rat la nhieu. No se giup ich cho phan bai tap cua minh rat la nhieu mong cac ban giup minh.

Minh se tim hieu ve thuat toan nay. Chac rang se co rat nhieu van de minh thac mac. Rat mong cac su phu chi gium nha

Chào bạn, ID3 chỉ là một trong các thuật giải của cây quyết định, nó có tên là ID3 vì nó sử dụng độ entropy, code cài đặt trên chỉ chạy demo thôi (áp dụng cho dữ liệu nhỏ), không thể áp dụng cho file dữ liệu lớn, có vấn đề j thì bạn gui qua minhlapb@gmail.com, thân chào.