form1.cs

使用C#实现的决策树算法实例

                //(11) 设Dj是D中满足输出j的数据元组的集合 //一个划分
                ArrayList Dj = (ArrayList)splittingCriterion.splitList[i];

                //(12) if Dj为空 then
                if (Dj.Count == 0)

                //(13) 加一个树叶到节点N，标记为D中的多数类
                {
                    TreeNode leaf = new TreeNode();
                    leaf.Text = FindMoreClass(d);
                    temp.Nodes.Add(leaf);
                }

                //(14) else 加一个由 Generate_decision_tree(Dj,attribute_list)返回的节点到节点N
                else
                {
                    TreeNode leaf = GenerateDecisionTree(Dj, new ArrayList(attribute_list));
                    leaf.Text = splittingCriterion.descriptionList[i].ToString() + "&&" + leaf.Text;
                    temp.Nodes.Add(leaf);
                }

                //     end for
            }

            //(15) 返回N
            return temp;
        }

        //寻找D中的同一类C，找到返回C的名称，找不到返回NULL。
        private string FindSameClass(ArrayList d)
        {
            Item temp = new Item();
            bool find;

            find = true;
            for (int i = 0; i < d.Count; i++)
            {
                if (i == 0)
                {
                    temp.buysComputer = ((Item)d[i]).buysComputer;
                }
                else
                {
                    if (temp.buysComputer != ((Item)d[i]).buysComputer)
                    {
                        find = false;
                        break;
                    }
                }
            }
            if (find) return "buysComputer=" + temp.buysComputer.ToString();

            return null;
        }

        //寻找D中的多数类
        private string FindMoreClass(ArrayList d)
        {
            int count = 0;
            string temp = "buysComputer=";
            for (int i = 0; i < d.Count; i++)
            {
                if (((Item)d[i]).buysComputer == buysComputerType.yes)
                    count++;
            }
            if (2 * count >= d.Count)
                return temp + "yes";
            else
                return temp + "no";

        }

        //找出“最好”的splitting_criterion
        private SplitCriterion AttributeSelectionMethod(ArrayList d, ArrayList attribute_list)
        {
            SplitCriterion splitting_criterion = new SplitCriterion();
            switch (attributeSelectionMethod)
            {
                case attributeSelectionMethodType.InformationGain:
                    //double info;           //按类划分的期望信息
                    double infoA;          //按A划分的期望信息
                    //double gainA;           //信息增益

                    //计算info
                    /*
                    info = Info(d);
                    */

                    //计算最小的InfoA和选择的属性
                    infoA = 1;
                    splitting_criterion.attribute = null;
                    for (int i = 0; i < attribute_list.Count; i++)
                    {
                        string a = (string)attribute_list[i];
                        double temp = 1;
                        switch (a)
                        {
                            case "age":
                                temp = InfoAge(d);
                                break;
                            case "income":
                                temp = InfoIncome(d);
                                break;
                            case "student":
                                temp = InfoStudent(d);
                                break;
                            case "creditRating":
                                temp = InfoCreditRating(d);
                                break;
                            default:
                                MessageBox.Show("error");
                                break;
                        }
                        if (temp < infoA)
                        {
                            splitting_criterion.attribute = a;
                            infoA = temp;
                        }
                    }

                    //计算gainA
                    /*
                    { }
                    */

                    //计算splitting_criterion
                    {
                        string[] type = Enum.GetNames(GetEnumType(splitting_criterion.attribute));
                        for (int i = 0; i < type.Length; i++)
                        {
                            ArrayList Dj = CopySmallCollection(d, splitting_criterion.attribute, type[i]);
                            splitting_criterion.descriptionList.Add(type[i]);
                            splitting_criterion.splitList.Add(Dj);
                        }
                    }
                    return splitting_criterion;

                case attributeSelectionMethodType.GainRate:
                    //double splitInfo;          //平均增益
                    double splitInfoA;         //按A划分的信息增益
                    double gainA;               //信息增益
                    double gainRatioA;          //信息增益率


                    //计算splitInfo
                    /*
                    splitInfo = SplitInfo(D);
                    */

                    //计算最大的gainRatioA和选择的属性
                    {
                        gainRatioA = 0;
                        splitting_criterion.attribute = null;
                        for (int i = 0; i < attribute_list.Count; i++)
                        {
                            string a = (string)attribute_list[i];
                            double temp = 0;
                            //计算gainA
                            gainA = GainA(a, d);
                            //计算splitInfoA
                            splitInfoA = SplitInfoA(a, d);
                            //计算gainRatioA
                            if (splitInfoA != 0)
                            {
                                temp = gainA / splitInfoA;
                            }
                            else
                            {
                                temp = 1;
                            }
                            if (temp > gainRatioA)
                            {
                                splitting_criterion.attribute = a;
                                gainRatioA = temp;
                            }
                        }
                    }

                    //计算splitting_criterion
                    {
                        string[] type = Enum.GetNames(GetEnumType(splitting_criterion.attribute));
                        for (int i = 0; i < type.Length; i++)
                        {
                            ArrayList Dj = CopySmallCollection(d, splitting_criterion.attribute, type[i]);
                            splitting_criterion.descriptionList.Add(type[i]);
                            splitting_criterion.splitList.Add(Dj);
                        }
                    }
                    return splitting_criterion;

                case attributeSelectionMethodType.Gini:
                    GiniSplit giniA = new GiniSplit();   //按A划分的最小gini

                    //计算最小giniA
                    {
                        giniA.gini = 1;
                        splitting_criterion.attribute = null;
                        for (int i = 0; i < attribute_list.Count; i++)
                        {
                            string a = (string)attribute_list[i];
                            GiniSplit temp;
                            //计算gini
                            temp = GiniA(a, d);
                            if (temp.gini < giniA.gini)
                            {
                                giniA = temp;
                            }
                        }
                    }

                    //计算splitting_criterion
                    splitting_criterion = giniA.giniSplitCriterion;
                    return splitting_criterion;

                default:
                    MessageBox.Show("error");
                    break;
            }
            return splitting_criterion;
        }

        //计算Info
        private double Info(ArrayList d)
        {
            double info = 0;
            double countYes = 0;
            for (int i = 0; i < d.Count; i++)
            {
                if (((Item)d[i]).buysComputer == buysComputerType.yes)
                    countYes++;
            }
            if (countYes != 0)
                info += -(countYes / d.Count) * Math.Log((countYes / d.Count), 2);
            if (countYes != d.Count)
                info += -((d.Count - countYes) / d.Count) * Math.Log(((d.Count - countYes) / d.Count), 2);
            return info;
        }

        //计算"age"属性的Info
        private double InfoAge(ArrayList d)
        {
            double youth = 0, middle_aged = 0, senior = 0;
            for (int i = 0; i < d.Count; i++)
            {
                switch (((Item)d[i]).age)
                {
                    case ageType.youth:
                        youth++;
                        break;
                    case ageType.middle_aged:
                        middle_aged++;
                        break;
                    case ageType.senior:
                        senior++;
                        break;
                    default:
                        MessageBox.Show("error");
                        break;
                }
            }
            return youth / d.Count * Info(CopySmallCollection(d, "age", ageType.youth)) + middle_aged / d.Count * Info(CopySmallCollection(d, "age", ageType.middle_aged)) + senior / d.Count * Info(CopySmallCollection(d, "age", ageType.senior));
        }

        //计算"income"属性的Info
        private double InfoIncome(ArrayList d)
        {
            double low = 0, medium = 0, high = 0;
            for (int i = 0; i < d.Count; i++)
            {
                switch (((Item)d[i]).income)
                {
                    case incomeType.low:
                        low++;
                        break;
                    case incomeType.medium:
                        medium++;
                        break;
                    case incomeType.high:
                        high++;
                        break;
                    default:
                        MessageBox.Show("error");
                        break;
                }
            }
            return low / d.Count * Info(CopySmallCollection(d, "income", incomeType.low)) + medium / d.Count * Info(CopySmallCollection(d, "income", incomeType.medium)) + high / d.Count * Info(CopySmallCollection(d, "income", incomeType.high));
        }

        //计算"student"属性的Info
        private double InfoStudent(ArrayList d)
        {
            double yes = 0, no = 0;
            for (int i = 0; i < d.Count; i++)
            {
                switch (((Item)d[i]).student)
                {
                    case studentType.yes:
                        yes++;
                        break;
                    case studentType.no:
                        no++;
                        break;
                    default:
                        MessageBox.Show("error");
                        break;
                }
            }
            return yes / d.Count * Info(CopySmallCollection(d, "student", studentType.yes)) + no / d.Count * Info(CopySmallCollection(d, "student", studentType.no));
        }

        //计算"creditRating"属性的Info
        private double InfoCreditRating(ArrayList d)
        {
            double excellent = 0, fair = 0;
            for (int i = 0; i < d.Count; i++)
            {