Logo

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