form1.cs

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

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using DecisionTree;

namespace DecisionTreeAlgorithm
{
    public partial class Form1 : Form
    {
        enum attributeSelectionMethodType { InformationGain, GainRate, Gini };
        enum ageType { youth, middle_aged, senior };
        enum incomeType { low, medium, high };
        enum studentType { yes, no };
        enum creditRatingType { fair, excellent };
        enum buysComputerType { yes, no };
        struct Item
        {
            public int ID;
            public ageType age;
            public incomeType income;
            public studentType student;
            public creditRatingType creditRating;
            public buysComputerType buysComputer;
        }

        private attributeSelectionMethodType attributeSelectionMethod;      //属性选择度量模式
        public ArrayList al;                                                //测试数据
        private ArrayList attributeList;


        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            attributeSelectionMethod = attributeSelectionMethodType.InformationGain;
            al = new ArrayList();
            this.Testdata.Items.Add("RID\tage\t\tincome\tstudent\tcredit_rating\tClass:buys_computer\n");
            attributeList = new ArrayList();
            cbAge.Items.Add("youth");
            cbAge.Items.Add("middle_aged");
            cbAge.Items.Add("senior ");
            comboBox2.Items.Add("low");
            comboBox2.Items.Add("medium");
            comboBox2.Items.Add("high");
            comboBox3.Items.Add("yes");
            comboBox3.Items.Add("no");
            comboBox4.Items.Add("fair");
            comboBox4.Items.Add("excellent");
            comboBox5.Items.Add("yes");
            comboBox5.Items.Add("no ");
            comboBox5.Items.Add("");
        }

        private void test1()
        {
            Item testItem;

            testItem = new Item();
            testItem.ID =al.Count+1;
            testItem.age = ageType.youth;
            testItem.income = incomeType.high;
            testItem.student = studentType.no;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.no;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.youth;
            testItem.income = incomeType.high;
            testItem.student = studentType.no;
            testItem.creditRating = creditRatingType.excellent;
            testItem.buysComputer = buysComputerType.no;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.middle_aged;
            testItem.income = incomeType.high;
            testItem.student = studentType.no;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.senior;
            testItem.income = incomeType.medium;
            testItem.student = studentType.no;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.senior;
            testItem.income = incomeType.low;
            testItem.student = studentType.yes;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.senior;
            testItem.income = incomeType.low;
            testItem.student = studentType.yes;
            testItem.creditRating = creditRatingType.excellent;
            testItem.buysComputer = buysComputerType.no;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.middle_aged;
            testItem.income = incomeType.low;
            testItem.student = studentType.yes;
            testItem.creditRating = creditRatingType.excellent;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.youth;
            testItem.income = incomeType.medium;
            testItem.student = studentType.no;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.no;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.youth;
            testItem.income = incomeType.low;
            testItem.student = studentType.yes;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.senior;
            testItem.income = incomeType.medium;
            testItem.student = studentType.yes;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.youth;
            testItem.income = incomeType.medium;
            testItem.student = studentType.yes;
            testItem.creditRating = creditRatingType.excellent;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.middle_aged;
            testItem.income = incomeType.medium;
            testItem.student = studentType.no;
            testItem.creditRating = creditRatingType.excellent;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.middle_aged;
            testItem.income = incomeType.high;
            testItem.student = studentType.yes;
            testItem.creditRating = creditRatingType.fair;
            testItem.buysComputer = buysComputerType.yes;
            al.Add(testItem);

            testItem = new Item();
            testItem.ID = al.Count+1;
            testItem.age = ageType.senior;
            testItem.income = incomeType.medium;
            testItem.student = studentType.no;
            testItem.creditRating = creditRatingType.excellent;
            testItem.buysComputer = buysComputerType.no;
            al.Add(testItem);
            AddDataToListbox(al);

        }

        private void AddDataToListbox(ArrayList al)
        {
            Item testItem = new Item();
            for (int i = 0; i < al.Count; i++)
            {
                string temp = "";
                testItem = (Item)al[i];
                temp += testItem.ID.ToString();
                temp += "\t";
                temp += testItem.age.ToString();
                temp += "\t";
                if (testItem.age.ToString().Length < 8)
                    temp += "\t";
                temp += testItem.income.ToString();
                temp += "\t";
                temp += testItem.student.ToString();
                temp += "\t";
                temp += testItem.creditRating.ToString();
                temp += "\t";
                if (testItem.creditRating.ToString().Length < 8)
                    temp += "\t";
                temp += testItem.buysComputer.ToString();
                temp += "\n";
                this.Testdata.Items.Add(temp);
            }
 
        }

        private void infomationGainToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.infomationGainToolStripMenuItem.Checked = true;
            this.gainRateToolStripMenuItem.Checked = false;
            this.giniToolStripMenuItem.Checked = false;
            attributeSelectionMethod = attributeSelectionMethodType.InformationGain;
        }

        private void gainRateToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.infomationGainToolStripMenuItem.Checked = false;
            this.gainRateToolStripMenuItem.Checked = true;
            this.giniToolStripMenuItem.Checked = false;
            attributeSelectionMethod = attributeSelectionMethodType.GainRate;
        }

        private void giniToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.infomationGainToolStripMenuItem.Checked = false;
            this.gainRateToolStripMenuItem.Checked = false;
            this.giniToolStripMenuItem.Checked = true;
            attributeSelectionMethod = attributeSelectionMethodType.Gini;
        }

        private void btnDTree_Click(object sender, EventArgs e)
        {
            if (Testdata.Items.Count == 1)
            {
                MessageBox.Show("Please Inport Test Data First");
            }
            attributeList.Clear();
            attributeList.Add("age");
            attributeList.Add("income");
            attributeList.Add("student");
            attributeList.Add("creditRating");

            switch (attributeSelectionMethod)
            {
                case attributeSelectionMethodType.InformationGain:
                    break;
                case attributeSelectionMethodType.GainRate:
                    break;
                case attributeSelectionMethodType.Gini:
                    break;
                default:
                    MessageBox.Show("error");
                    break;
            }
            this.DecisionTree.Nodes.Clear();
            this.DecisionTree.Nodes.Add(GenerateDecisionTree(al, attributeList));
        }

        //算法：Generate_decision_tree。由数据划分D的训练元组产生决策树。
        private TreeNode GenerateDecisionTree(ArrayList d, ArrayList attribute_list)
        {
            //(1)  创建一个节点N
            TreeNode temp = new TreeNode();

            //(2)  ifD中的元组都是同一类C then
            string C = FindSameClass(d);
            if (C != null)

            //(3)  返回N作为叶节点，以类C标记
            {
                temp.Text = C;
                return temp;
            }

            //(4)  if attribute_list为空 then
            if (attribute_list.Count == 0)

            //(5)  返回N作为叶子节点，标记为D中的多数类；//多数表决
            {
                temp.Text = FindMoreClass(d);
                return temp;
            }

            //(6)  使用attribute_selection_method(D,attribute_list)，找出“最好”的splitting_criterion
            SplitCriterion splittingCriterion = AttributeSelectionMethod(d, attribute_list);

            //(7)  用splitting_criterion标记节点N
            temp.Text = splittingCriterion.attribute;

            //(8)  if splitting_attribute是离散值的并且允许多路划分 then //不限于二叉树
            if (true)//假定总是离散的并且允许多路划分

            //(9)  attribute_list<--attribute_list-splitting_attribute //删除划分属性
            {
                attribute_list.Remove(splittingCriterion.attribute);
            }

            //(10) for splitting_criterion的每个输出j //划分元组并对每个划分产生子树            
            for (int i = 0; i < splittingCriterion.splitList.Count; i++)
            {