决策树简单介绍(二) Accord.Net中决策树的贯彻和下

 

Strong

Normal

D10

D14

High

Weak

D7

Weak

Sunny

Mitchell’s Tennis Example

属性、方法

含义

Root

根节点

Attributes

标识各个特征的信息(连续、离散、范围)

InputCount

特征个数

OutputClasses

输出类别种数

Compute()

计算出某一样本的类别信息

Load(),Save()

将决策树存储到文件或者读出

ToAssembly()

存储到dll程序集中

 

Yes

D11

   
 以地方的于网球例子,这里被出Accord.Net中结构和教练决策树的代码示例。

Weak

D1

D2

Cool

Yes

Yes

Yes

     
这里以一个藏的于网球的事例,介绍ID3算法的读书过程。要理解下面的代码可能用针对决策树的就学过程有个着力的垂询,可以参照开头为起底链接学习下决策树的基本概念。

Outlook

No

Weak

Rain

Normal

Normal

 

Weak

      还出另外因项就不再逐一介绍了,Accord的法定文档里还出更进一步鲜明的授课。

Overcast

     
这里坐一个经的打网球的事例,介绍ID3算法的求学过程。要明白下面的代码可能要对决策树的念过程发生只中心的打听,可以参照开头为出底链接学习下决策树的基本概念。

Yes

D10

No

      C4.5之贯彻同ID3到底法流程基本相同,有几个不同之处

      

Mild

Overcast

Yes

Mild

Rain

仲裁树结构

Yes

    网球 1

Rain

 

D9

网球 2

    网球 3

 

网球 4

     
主要想只要说之凡ID3Learning和C45Learning两单近乎。这是Accord.Net实现之简单独裁定树学(训练)算法,ID3算法和C4.5算法(ID为Iterative
Dichotomiser的缩写,迭代二分器;C是Classifier的缩写,即第4.5替代分类器)。后面会介绍两者的别。

Wind

     
此代码仅为便利了解,具体贯彻细节要自行下载Accord源代码阅读,相信你见面有成百上千取。

     
Accord.Net(http://accord-framework.net/)是一个开源之.Net环境下实现的机器上到底法库。并且还包了微机视觉、图像处理、数据解析等等许多算法,并且多都是为此C#编纂的,对于.Net程序员十分投机。代码在Github托管,并且现在按当保护着。(https://github.com/accord-net/framework)。此处不再具体介绍,有趣味之可去官网或Github下充斥文档和代码深入了解。此处就简单介绍决策树有的兑现和采取方法。

Mild

      简单介绍下要性能方法。

Weak

      2)
C4.5支撑连续型特征,因此,在递归进行事先,要动用二私分效仿计算出n-1只候选划分点,将这些划分点当做离散变量处理就与ID3经过一样了。同样是以连续型变量,这样同样漫漫路线下连续型特征可以屡屡因此来分,而离散型特征每个只能用相同差。

Hot

     
决策树是一律好像机器上算法,可以实现对数据集的分类、预测等。具体要看我别一样首博客(http://www.cnblogs.com/twocold/p/5424517.html)。

 

D3

D4

D4

     

Normal

      还有树结构:

No

PlayTennis

        /// <summary>
        /// 决策树学习的分割构造递归方法
        /// </summary>
        /// <param name="root">当前递归结点</param>
        /// <param name="input">输入样本特征</param>
        /// <param name="output">样本对应类别</param>
        /// <param name="height">当前结点层数</param>
        private void split(DecisionNode root, int[][] input, int[] output, int height)
        {
            //递归return条件

            //1.如果output[]都相等,就是说当前所有样本类别相同,则递归结束。结点标记为叶子节点,output值标识为样本类别值           

            double entropy = Statistics.Tools.Entropy(output, outputClasses);

            if (entropy == 0)
            {
                if (output.Length > 0)
                    root.Output = output[0];
                return;
            }

            //2.如果当前路径上所有特征都用过一次了,也就是说现在所有样本在所有特征上取值相同,也就没法划分了;递归结束。结点标记为叶子节点,output值标识为样本类别值最多的那个

            //这个变量存储的是还未使用的特征个数
            int candidateCount = attributeUsageCount.Count(x => x < 1);

            if (candidateCount == 0)
            {
                root.Output = Statistics.Tools.Mode(output);
                return;
            }


            // 如果需要继续分裂,则首先寻找最优分裂特征,
            // 存储剩余所有可以特征的信息增益大小
            double[] scores = new double[candidateCount];
            // 循环计算每个特征分裂时的信息增益存储到scores里

            Parallel.For(0, scores.Length, i =>

            {
                scores[i] = computeGainRatio(input, output, candidates[i],
                    entropy, out partitions[i], out outputSubs[i]);
            }

            // 获取到最大信息增益对应的特征
            int maxGainIndex = scores.Max();
            // 接下来 需要按照特征的值分割当前的dataset,然后传递给子节点 递归
            DecisionNode[] children = new DecisionNode[maxGainPartition.Length];

            for (int i = 0; i < children.Length; i++)
            {
                int[][] inputSubset = input.Submatrix(maxGainPartition[i]);

                split(children[i], inputSubset, outputSubset, height + 1); // 递归每个子节点

            }

            root.Branches.AddRange(children);

        }

Yes

        首先观察树结构面临极度紧要的一个结构,Node类的类图如下:

Weak

      决策树、顾名思义,肯定是一个与培训结构,作为最基础之数据结构之一,我们获悉树结构的灵活性。那么Accord.Net是怎么样贯彻这种结构的也?看类图

        首先观察树结构面临不过紧要的一个组织,Node类的类图如下:

属性

含义

IsLeaf

是否为叶子节点

IsRoot

是否为根节点

Output

指示结点的类别信息(叶子节点可用)

Value

为非根节点时,表示其父节点分割特征的值

Branches

为非叶子节点时,表示其子结点的集合

High

Yes

D14

D5

High

     
此代码仅为利清楚,具体贯彻细节要自行下载Accord源代码阅读,相信您会出为数不少到手。

 

High

Humidity

Weak

Normal

Cool

核定树介绍

      1)
在选择最为优分割特征时,ID3算法采用的凡信息增益,C4.5使的是增益率。

Sunny

      3) C4.5支持缺失值的处理,遗憾之是Accord中连从未在这同一特色。

D11

Rain

Sunny

Overcast

Mild

Normal

    贴平摆设采用决策树做的小例子。

 

     
Accord.Net(http://accord-framework.net/)是一个开源之.Net环境下促成之机械上到底法库。并且还包了计算机视觉、图像处理、数据解析等等许多算法,并且大多都是故C#修的,对于.Net程序员十分要好。代码在Github托管,并且现在按在护着。(https://github.com/accord-net/framework)。此处不再具体介绍,有趣味之足去官网或Github下充斥文档和代码深入了解。此处就简简单单介绍决策树有的贯彻与使用方法。

    贴平摆放采用决策树做的小例子。

D9

High

Cool

决定树结构

Normal

D1

Mitchell’s Tennis Example

D6

Rain

      

 

Strong

Accord.Net

Yes

No

 

Weak

Temperature

Weak

Hot

      3) C4.5支撑缺失值的拍卖,遗憾的凡Accord中连从未在这等同特色。

High

    网球 5

 

属性

含义

IsLeaf

是否为叶子节点

IsRoot

是否为根节点

Output

指示结点的类别信息(叶子节点可用)

Value

为非根节点时,表示其父节点分割特征的值

Branches

为非叶子节点时,表示其子结点的集合

No

No

D8

Yes

Yes

Normal

High

D3

     
下面贴出ID3算是法中递归方法的伪代码,大致讲解下该实现逻辑(注:此代码删去了过多细节,因此无法运行,只盖了解其实现逻辑。)。

     Accord.Net中尚被起了简短的剪枝算法,有趣味可以自动阅读。

     

High

 

网球 6

Cool

Rain

High

Temperature

Cool

Strong

Normal

D5

Sunny

Hot

Day

      首先,为了后面更是组织决策树,我们需要将地方的数简化一下,以字符串存储和进行比会损耗大量之内存空间,并且降低效率。考虑到有特征都也离散特征,可以一直用最为简便易行的整型表示虽行,只要保存下数字和字符串的呼应关系就推行。Accord.Net用了CodeBook来落实,这里为便无现实介绍了。然后用对树的一部分性质进行初始化,比如特征的个数(InputCount),类别数(OutputClasses)。还有每个特征可能的取值个数。接下来就好用方面codebook转义过的样书数开展结构了。

No

Mild

Hot

      C4.5底落实与ID3总算法流程基本相同,有几乎单不同之处

      

Cool

Yes

Yes

Mild

Normal

D13

Rain

PlayTennis

      决策树、顾名思义,肯定是一个以及塑造结构,作为最基础的数据结构之一,我们获悉树结构的灵活性。那么Accord.Net是哪贯彻这种结构的也?看类图

Weak

Strong

Strong

Hot

Overcast

Normal

     
主要想只要说的凡ID3Learning和C45Learning两只类似。这是Accord.Net实现之一定量个裁定树学(训练)算法,ID3算法和C4.5算法(ID为Iterative
Dichotomiser的缩写,迭代二分器;C是Classifier的缩写,即第4.5代表分类器)。后面会介绍两者的分别。

Yes

Strong

D13

High

Strong

    网球 7

Outlook

High

Hot

   
 以地方的于网球例子,这里被出Accord.Net中结构与教练决策树的代码示例。

      简单介绍下要性能方法。

     Accord.Net中尚叫起了简要的剪枝算法,有趣味可以自动阅读。

Sunny

Strong

Overcast

Sunny

D2

Sunny

Day

Cool

 

No

 

D12

Strong

Overcast

D6

Sunny

Weak

Mild

Weak

 

Mild

 

Yes

Normal

Cool

Weak

Normal

Sunny

      2)
C4.5支撑连续型特征,因此,在递归进行事先,要采取二细分效仿计算出n-1只候选划分点,将这些划分点当做离散变量处理便跟ID3历程同样了。同样是为连续型变量,这样同样修路下连续型特征可以频繁据此来划分,而离散型特征每个只能用同破。

Accord.Net

Strong

Overcast

D12

Humidity

 

属性、方法

含义

Root

根节点

Attributes

标识各个特征的信息(连续、离散、范围)

InputCount

特征个数

OutputClasses

输出类别种数

Compute()

计算出某一样本的类别信息

Load(),Save()

将决策树存储到文件或者读出

ToAssembly()

存储到dll程序集中

Overcast

网球 8

     
决策树是同等近乎机器上算法,可以实现对数据集的归类、预测等。具体要看我别一样首博客(http://www.cnblogs.com/twocold/p/5424517.html)。

D7

Mild

Yes

Sunny

No

仲裁树学算法:

           //数据输入 存储为DataTable
             DataTable data = new DataTable("Mitchell's Tennis Example");
            data.Columns.Add("Day");
            data.Columns.Add("Outlook");
            data.Columns.Add("Temperature");
            data.Columns.Add("Humidity");
            data.Columns.Add("Wind");
            data.Columns.Add("PlayTennis");

            data.Rows.Add("D1", "Sunny", "Hot", "High", "Weak", "No");
            data.Rows.Add("D2", "Sunny", "Hot", "High", "Strong", "No");
            data.Rows.Add("D3", "Overcast", "Hot", "High", "Weak", "Yes");
            data.Rows.Add("D4", "Rain", "Mild", "High", "Weak", "Yes");
            data.Rows.Add("D5", "Rain", "Cool", "Normal", "Weak", "Yes");
            data.Rows.Add("D6", "Rain", "Cool", "Normal", "Strong", "No");
            data.Rows.Add("D7", "Overcast", "Cool", "Normal", "Strong", "Yes");
            data.Rows.Add("D8", "Sunny", "Mild", "High", "Weak", "No");
            data.Rows.Add("D9", "Sunny", "Cool", "Normal", "Weak", "Yes");
            data.Rows.Add("D10", "Rain", "Mild", "Normal", "Weak", "Yes");
            data.Rows.Add("D11", "Sunny", "Mild", "Normal", "Strong", "Yes");
            data.Rows.Add("D12", "Overcast", "Mild", "High", "Strong", "Yes");
            data.Rows.Add("D13", "Overcast", "Hot", "Normal", "Weak", "Yes");
            data.Rows.Add("D14", "Rain", "Mild", "High", "Strong", "No");
            // 创建一个CodeBook对象,用于将data中的字符串“翻译”成整型
            Codification codebook = new Codification(data,
              "Outlook", "Temperature", "Humidity", "Wind", "PlayTennis");
            // 将data中的样本特征数据部分和类别信息分别转换成数组
            DataTable symbols = codebook.Apply(data);
            int[][] inputs = Matrix.ToArray<double>(symbols, "Outlook", "Temperature", "Humidity", "Wind");
            int[] outputs = Matrix.ToArray<int>(symbols, "PlayTennis");
            //分析得出每个特征的信息,如,每个特征的可取值个数。
           DecisionVariable[] attributes = DecisionVariable.FromCodebook(codebook, "Outlook", "Temperature", "Humidity", "Wind");

           int classCount = 2; //两种可能的输出,打网球和不打

            //根据参数初始化一个树结构
            DecisionTree tree = new DecisionTree(attributes, classCount);

            // 创建一个ID3训练方法
            ID3Learning id3learning = new ID3Learning(tree);

            // 训练该决策树
            id3learning.Run(inputs, outputs);

            //现在即可使用训练完成的决策树预测一个样本,并借助codebook“翻译”回来
            string answer = codebook.Translate("PlayTennis",tree.Compute(codebook.Translate("Sunny", "Hot", "High", "Strong")));

Wind

Mild

D8

决策树介绍

     
下面贴起ID3终于法中递归方法的伪代码,大致讲解下其落实逻辑(注:此代码删去了广大细节,因此无法运转,只约了解该落实逻辑。)。

Hot

        /// <summary>
        /// 决策树学习的分割构造递归方法
        /// </summary>
        /// <param name="root">当前递归结点</param>
        /// <param name="input">输入样本特征</param>
        /// <param name="output">样本对应类别</param>
        /// <param name="height">当前结点层数</param>
        private void split(DecisionNode root, int[][] input, int[] output, int height)
        {
            //递归return条件

            //1.如果output[]都相等,就是说当前所有样本类别相同,则递归结束。结点标记为叶子节点,output值标识为样本类别值           

            double entropy = Statistics.Tools.Entropy(output, outputClasses);

            if (entropy == 0)
            {
                if (output.Length > 0)
                    root.Output = output[0];
                return;
            }

            //2.如果当前路径上所有特征都用过一次了,也就是说现在所有样本在所有特征上取值相同,也就没法划分了;递归结束。结点标记为叶子节点,output值标识为样本类别值最多的那个

            //这个变量存储的是还未使用的特征个数
            int candidateCount = attributeUsageCount.Count(x => x < 1);

            if (candidateCount == 0)
            {
                root.Output = Statistics.Tools.Mode(output);
                return;
            }


            // 如果需要继续分裂,则首先寻找最优分裂特征,
            // 存储剩余所有可以特征的信息增益大小
            double[] scores = new double[candidateCount];
            // 循环计算每个特征分裂时的信息增益存储到scores里

            Parallel.For(0, scores.Length, i =>

            {
                scores[i] = computeGainRatio(input, output, candidates[i],
                    entropy, out partitions[i], out outputSubs[i]);
            }

            // 获取到最大信息增益对应的特征
            int maxGainIndex = scores.Max();
            // 接下来 需要按照特征的值分割当前的dataset,然后传递给子节点 递归
            DecisionNode[] children = new DecisionNode[maxGainPartition.Length];

            for (int i = 0; i < children.Length; i++)
            {
                int[][] inputSubset = input.Submatrix(maxGainPartition[i]);

                split(children[i], inputSubset, outputSubset, height + 1); // 递归每个子节点

            }

            root.Branches.AddRange(children);

        }

Strong

No

Rain

High

Mild

 

Rain

           //数据输入 存储为DataTable
             DataTable data = new DataTable("Mitchell's Tennis Example");
            data.Columns.Add("Day");
            data.Columns.Add("Outlook");
            data.Columns.Add("Temperature");
            data.Columns.Add("Humidity");
            data.Columns.Add("Wind");
            data.Columns.Add("PlayTennis");

            data.Rows.Add("D1", "Sunny", "Hot", "High", "Weak", "No");
            data.Rows.Add("D2", "Sunny", "Hot", "High", "Strong", "No");
            data.Rows.Add("D3", "Overcast", "Hot", "High", "Weak", "Yes");
            data.Rows.Add("D4", "Rain", "Mild", "High", "Weak", "Yes");
            data.Rows.Add("D5", "Rain", "Cool", "Normal", "Weak", "Yes");
            data.Rows.Add("D6", "Rain", "Cool", "Normal", "Strong", "No");
            data.Rows.Add("D7", "Overcast", "Cool", "Normal", "Strong", "Yes");
            data.Rows.Add("D8", "Sunny", "Mild", "High", "Weak", "No");
            data.Rows.Add("D9", "Sunny", "Cool", "Normal", "Weak", "Yes");
            data.Rows.Add("D10", "Rain", "Mild", "Normal", "Weak", "Yes");
            data.Rows.Add("D11", "Sunny", "Mild", "Normal", "Strong", "Yes");
            data.Rows.Add("D12", "Overcast", "Mild", "High", "Strong", "Yes");
            data.Rows.Add("D13", "Overcast", "Hot", "Normal", "Weak", "Yes");
            data.Rows.Add("D14", "Rain", "Mild", "High", "Strong", "No");
            // 创建一个CodeBook对象,用于将data中的字符串“翻译”成整型
            Codification codebook = new Codification(data,
              "Outlook", "Temperature", "Humidity", "Wind", "PlayTennis");
            // 将data中的样本特征数据部分和类别信息分别转换成数组
            DataTable symbols = codebook.Apply(data);
            int[][] inputs = Matrix.ToArray<double>(symbols, "Outlook", "Temperature", "Humidity", "Wind");
            int[] outputs = Matrix.ToArray<int>(symbols, "PlayTennis");
            //分析得出每个特征的信息,如,每个特征的可取值个数。
           DecisionVariable[] attributes = DecisionVariable.FromCodebook(codebook, "Outlook", "Temperature", "Humidity", "Wind");

           int classCount = 2; //两种可能的输出,打网球和不打

            //根据参数初始化一个树结构
            DecisionTree tree = new DecisionTree(attributes, classCount);

            // 创建一个ID3训练方法
            ID3Learning id3learning = new ID3Learning(tree);

            // 训练该决策树
            id3learning.Run(inputs, outputs);

            //现在即可使用训练完成的决策树预测一个样本,并借助codebook“翻译”回来
            string answer = codebook.Translate("PlayTennis",tree.Compute(codebook.Translate("Sunny", "Hot", "High", "Strong")));

      还有树结构:

Yes

Weak

Weak

Normal

High

Strong

      

      首先,为了后面更组织决策树,我们要把地方的多少简化一下,以字符串存储和进展较会损耗大量底内存空间,并且降低效率。考虑到所有特征都也离散特征,可以直接用最为简便易行的整型表示虽实施,只要保存下数字与字符串的对应关系就尽。Accord.Net用了CodeBook来贯彻,这里为就是无现实介绍了。然后用对树的一部分性进行初始化,比如特征的个数(InputCount),类别数(OutputClasses)。还有每个特征可能的取值个数。接下来就是得采取点codebook转义过之样书数进行结构了。

      1)
在选择最为优分割特征时,ID3算法采用的是信增益,C4.5采取的凡增益率。

仲裁树学算法:

High

Mild

Rain

Hot

      还产生其它因项就不再逐一介绍了,Accord的合法文档里都发生更加清楚的任课。