四、使用树加快查找和修改

树是最先进、最复杂的数据结构之一。它为图论打开了大门，图论被用来表示对象之间的关系。对象可以是任何类型，只要它们有一个确定的关系，就可以用树的形式来表示。

虽然有几十棵树，但不可能在一章中涵盖所有树，因此我们将采取不同的方法，并在浏览示例时以更实用的方式了解树，而不是像前几章那样提前了解树。

在本章中，我们将探讨以下主题:

  • 创建基本角度应用，
  • 使用 trie 树创建提前类型查找组件
  • 使用 ID3 算法创建信用卡批准预测器。

所以，让我们深入研究一下。

创建角度应用

在我们实现任何树之前，让我们建立一个基础应用，我们可以在后续的例子中使用它。

就像我们在前面章节中所做的那样，我们将使用 Angular CLI 创建一个 Angular 应用，使用以下步骤:

  1. 使用以下命令安装角度命令行界面(如果尚未完成):
npm install -g @angular/cli
  1. 通过运行以下命令，在您选择的文件夹中创建新项目:
ng new <project-name>

完成这两个步骤后，您应该能够看到新项目已经创建，所有相应的节点模块都已经安装完毕并准备就绪。

  1. 要运行应用，请从终端运行以下命令:
ng serve

创建提前类型查找

想象一下，你有一个用户注册表格，你的用户必须填写他们的信息，包括他们的国家。幸运的是，我们只有固定数量的国家，所以填充和选择的用户体验可以变得非常有趣和容易，而不是让他们滚动数百个选项。

在这个例子中，我们将创建一个 trie 树，并用所有国家的列表预先填充它。然后用户可以输入他们国家的名称，我们的组件将作为一个提前输入，并向用户显示可用的选项。

现在让我们讨论一下为什么我们需要一棵 trie 树。根据维基百科，以下是简单 trie 树的定义:

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree — an ordered tree data structure that is used to store a dynamic set or associate array where the keys are usually strings

换句话说，trie 树是一个优化的搜索树，其中的关键字是字符串。让我们用一个简单的例子来说明:

让我们考虑一下我们有一个字符串数组:

var friends = [ 'ross', 'rachel', 'adam', 'amy', 'joey'];

当将其转换为trie树时，会如下所示:

从上图中，我们可以注意到树从根开始，然后根据输入字符串，构建树。将字符串插入trie树时，单词被分解成单个字符，然后重复的节点不会被重新插入，而是被重新用于构建树的其余部分。

创建 trie 树

现在让我们创建trie树，我们将在我们的应用中使用它。在我们的应用中，让我们首先在src文件夹下创建名为utils的目录，我们将在其中添加我们的trie.ts文件。

我们的树的 API 将非常简洁，只有两种方法:

  • add() :给trie树添加元素
  • search():接受输入字符串，返回与查询字符串匹配的子树:
import {Injectable} from "@angular/core";

@Injectable()
export class Trie {
    tree: any = {};

    constructor() {}

}

创建后，让我们将其注入到app.module.ts中列出的主模块的提供者列表中，以便我们的组件可以访问树，如下所示:

import { BrowserModule } from '@angular/platform-browser';
import { NgModule } from '@angular/core';
import { FormsModule } from '@angular/forms';

import { AppComponent } from './app.component';
import {Trie} from "./utils/trie";

@NgModule({
  declarations: [
    AppComponent
  ],
  imports: [
    BrowserModule,
    FormsModule
  ],
  providers: [
      Trie
  ],
  bootstrap: [AppComponent]
})
export class AppModule { }

实现 add()方法

现在，我们的树已经准备好实现它的第一个方法。我们的树从没有元素开始(也就是一个空对象)。您可以使用任何数据结构来实现，但是为了简单起见，我们将使用对象作为我们的数据存储:

add(input) {
    // set to root of tree
    var currentNode = this.tree;

    // init next value
    var nextNode = null;

    // take 1st char and trim input
    // adam for ex becomes a and dam
    var curChar = input.slice(0,1);
    input = input.slice(1);

    // find first new character, until then keep trimming input
    while(currentNode[curChar] && curChar){
        currentNode = currentNode[curChar];

        // trim input
        curChar = input.slice(0,1);
        input = input.slice(1);
    }

    // while next character is available keep adding new branches and 
    // prune till end
    while(curChar) {
        // new reference in each loop
        nextNode = {};

        // assign to current tree node
        currentNode[curChar] = nextNode;

        // hold reference for next loop
        currentNode = nextNode;

        // prepare for next iteration
        curChar = input.slice(0,1);
        input = input.slice(1);
    }
}

正如您在前面的代码中看到的，该方法由以下两个步骤组成:

  1. 确定树已经构建到什么级别，并忽略这些字符。
  2. 将剩余部分作为一个新的子树添加，并一直持续到最后。

朋友们的例子

让我们把我们的知识用在一个例子中，在这个例子中，我们的用户想要给这个树添加两个元素，亚当，和阿德里安。首先，我们将把亚当 添加到树中，这样我们就有了节点ada和 m 。然后，当添加阿德里安时，我们检查已经添加的内容——在这种情况下是 a 和d——因此单词 rian 的剩余部分被添加为新的子树。

**记录后，我们会看到以下内容:

从前面的截图中可以看到， a 和 d 对于这两个单词都是通用的，然后剩下的就是我们添加的每个字符串的两个子树。

实现 search()方法

search()方法更简单高效，复杂度为 O(n)，其中 n 是搜索输入的长度。大 O 符号将在后面的章节中详细介绍:

search(input) {
    // get the whole tree
    var currentNode = this.tree;
    var curChar = input.slice(0,1);

    // take first character
    input = input.slice(1);

   // keep extracting the sub-tree based on the current character
    while(currentNode[curChar] && curChar){
        currentNode = currentNode[curChar];
        curChar = input.slice(0,1);
        input = input.slice(1);
    }

    // reached the end and no sub-tree found
    // e.g. no data found
    if (curChar && !currentNode[curChar]) {
        return {};
    }

    // return the node found
    return currentNode;
}

让我们以前面代码中描述的朋友为例。例如，如果用户键入 a，，我们使用刚刚实现的search()方法提取子树。我们得到一个下面的子树。

用户提供的输入字符越多，响应对象就越精细:

从前面的截图中我们可以看到，随着用户输入的越来越多，我们的search()方法不断返回与之匹配的节点的子树，同时在它下面可以看到整个树。为了在屏幕上呈现它，我们使用了以下代码。

在我们的app.component.ts文件中，我们添加了以下内容，它查询了Trie类上的search()方法:

import { Component } from '@angular/core';
import {Trie} from "../utils/trie";

@Component({
    selector: 'app-root',
    templateUrl: './app.component.html',
    styleUrls: ['./app.component.css']
})
export class AppComponent {
    countries = ["Afghanistan","Albania","Algeria",...,"Yemen","Zambia","Zimbabwe"];
    searchResp = [];

    constructor(private trie : Trie) {
        this.countries.forEach((c) => {
            this.trie.add(c); 
        });
    }

    search(key) {
        this.searchResp = this.trie.search(key).remainder;
    }
}

然后使用简单的pre标签将该搜索结果绑定到模板:

<pre>{{searchResp}}</pre>

在节点处保留余数

我们之前实现的search()方法很好用；然而，作为一名开发人员，您现在需要遍历返回的子树，并从中构造出单词的剩余部分，以显示在 UI 上。那有点麻烦，不是吗？如果我们可以简化它，让树返回子树以及它们所形成的单词的剩余部分，会怎么样？实际上，实现这一点相当容易。

我们将需要对我们的算法做一个小的改变，并在每个节点添加余数集；这样，只要识别出一个节点，我们就可以将剩余的节点添加到该集合中，并且在创建新节点的同时将新的元素推送到该集合中。让我们看看这是如何修改我们的代码的:

add(input) {
    // set to root of tree
    var currentNode = this.tree;

    // init value
    var nextNode = null;

    // take 1st char and trim input
    var curChar = input.slice(0,1);
    input = input.slice(1);

    // find first new character, until then keep triming input
    while(currentNode[curChar] && curChar){
        currentNode = currentNode[curChar];

        // update remainder array, this will exist as we added the node
        earlier
        currentNode.remainder.push(input);

        // trim input
        curChar = input.slice(0,1);
        input = input.slice(1);
    }

    // while next character is available keep adding new branches and
    prune till end
    while(curChar) {
        // new reference in each loop
        // create remainder array starting with current input
        // so when adding the node `a` we add to the remainder `dam`
        and so on
        nextNode = {
            remainder: [input]
        };

        // assign to current tree node
        currentNode[curChar] = nextNode;

        // hold reference for next loop
        currentNode = nextNode;

        // prepare for next iteration
        curChar = input.slice(0,1);
        input = input.slice(1);
    }
}

正如您在前面的代码中所看到的，添加两行代码使我们的工作比以前容易多了。不再有不必要的子树对象循环，我们返回子树每个节点的剩余单词:

这也意味着我们必须更新我们的search()方法的失败条件，以返回一个设置了remainder的空对象，而不是一个空对象，这与前面不同:

search(input) {
    var currentNode = this.tree;
    var curChar = input.slice(0,1);

    input = input.slice(1);

    while(currentNode[curChar] && curChar){
        currentNode = currentNode[curChar];
        curChar = input.slice(0,1);
        input = input.slice(1);
    }

    if (curChar && !currentNode[curChar]) {
        return {
            remainder: [] 
        };
    }

    return currentNode;
}

最终形式

将所有这些放在一起，并对我们的用户界面进行简单的更改，我们最终可以通过列表进行搜索，并以非常快速有效的方式显示结果。

结合之前的变更，我们的app.component.ts已经准备好采用它的最终形式:

import { Component } from '@angular/core';
import {Trie} from "../utils/trie";

@Component({
    selector: 'app-root',
    templateUrl: './app.component.html',
    styleUrls: ['./app.component.css']
})
export class AppComponent {
    countries = ["Afghanistan","Albania","Algeria","Andorra","Angola","Anguilla","Antigua & Barbuda","Argentina","Armenia","Aruba","Australia","Austria","Azerbaijan","Bahamas","Bahrain","Bangladesh","Barbados","Belarus","Belgium","Belize","Benin","Bermuda","Bhutan","Bolivia","Bosnia & Herzegovina","Botswana","Brazil","British Virgin Islands","Brunei","Bulgaria","Burkina Faso","Burundi","Cambodia","Cameroon","Cape Verde","Cayman Islands","Chad","Chile","China","Colombia","Congo","Cook Islands","Costa Rica","Cote D Ivoire","Croatia","Cruise Ship","Cuba","Cyprus","Czech Republic","Denmark","Djibouti","Dominica","Dominican Republic","Ecuador","Egypt","El Salvador","Equatorial Guinea","Estonia","Ethiopia","Falkland Islands","Faroe Islands","Fiji","Finland","France","French Polynesia","French West Indies","Gabon","Gambia","Georgia","Germany","Ghana","Gibraltar","Greece","Greenland","Grenada","Guam","Guatemala","Guernsey","Guinea","Guinea Bissau","Guyana","Haiti","Honduras","Hong Kong","Hungary","Iceland","India","Indonesia","Iran","Iraq","Ireland","Isle of Man","Israel","Italy","Jamaica","Japan","Jersey","Jordan","Kazakhstan","Kenya","Kuwait","Kyrgyz Republic","Laos","Latvia","Lebanon","Lesotho","Liberia","Libya","Liechtenstein","Lithuania","Luxembourg","Macau","Macedonia","Madagascar","Malawi","Malaysia","Maldives","Mali","Malta","Mauritania","Mauritius","Mexico","Moldova","Monaco","Mongolia","Montenegro","Montserrat","Morocco","Mozambique","Namibia","Nepal","Netherlands","Netherlands Antilles","New Caledonia","New Zealand","Nicaragua","Niger","Nigeria","Norway","Oman","Pakistan","Palestine","Panama","Papua New Guinea","Paraguay","Peru","Philippines","Poland","Portugal","Puerto Rico","Qatar","Reunion","Romania","Russia","Rwanda","Saint Pierre & Miquelon","Samoa","San Marino","Satellite","Saudi Arabia","Senegal","Serbia","Seychelles","Sierra Leone","Singapore","Slovakia","Slovenia","South Africa","South Korea","Spain","Sri Lanka","St Kitts & Nevis","St Lucia","St Vincent","St. Lucia","Sudan","Suriname","Swaziland","Sweden","Switzerland","Syria","Taiwan","Tajikistan","Tanzania","Thailand","Timor L'Este","Togo","Tonga","Trinidad & Tobago","Tunisia","Turkey","Turkmenistan","Turks & Caicos","Uganda","Ukraine","United Arab Emirates","United Kingdom","Uruguay","Uzbekistan","Venezuela","Vietnam","Virgin Islands (US)","Yemen","Zambia","Zimbabwe"];
    searchResp = [];

    constructor(private trie : Trie) {
        this.countries.forEach((c) => {
            this.trie.add(c); 
        });
    }

    search(key) {
        this.searchResp = this.trie.search(key).remainder;
    }
}

同样，更新app.component.html模板以显示搜索结果:

<input type="text" placeholder="search countries" #searchInp (keyup)="search(searchInp.value)" />

<div *ngFor="let resp of searchResp">
    <strong>{{searchInp.value}}</strong>{{resp}}
</div>

<div *ngIf="searchInp.value && !searchResp.length">
    No results found for {{searchInp.value}}
</div>

结果如下:

创建信用卡审批预测

树木无处不在。无论您使用什么应用，内部都有树在发挥作用。说到这里，并不是所有的树都是数据结构。在这个例子中，我们将探索一些不同的东西，这是一个真正流行但不是典型的数据结构，也就是决策树。

在某个阶段，你会遇到某种自动预测系统。无论是预测比赛获胜者的体育网站，还是告诉你应该申请哪张信用卡以获得快速批准的信用评分网站。在这个例子中，我们将使用信用卡批准预测器，但这可以很容易地转移到您选择的任何应用。

在大多数情况下，我们有一个复杂的机器学习模型在幕后运行，以生成准确的预测，但是，因为我们知道影响批准或拒绝的因素数量是有限的，所以我们可以使用决策树根据过去展示的模式来确定批准的机会。以下是我们在此示例中必须完成的任务列表:

  1. 通过实施迭代二分器 3 ( ID3 )算法来创建决策树，以对未来样本进行分类。
  2. 创建训练数据集。
  3. 通过算法运行新的输入并验证响应。

ID3 算法

到目前为止，我们看到的算法并不是很复杂；它们相当琐碎，我们主要关注的是为特定的数据结构实现 API。在这个例子中，没有要实现的数据结构；算法本身会生成我们将用于应用的决策树。

首先，让我们看看历史数据表是如何转换成决策树的。初步形成的树由决策节点(表示决策)和叶节点(表示最终响应，如是或否)组成。根据数据集的不同，决策节点可以有两个或多个子节点。然而，树必须从某个地方开始，对吗？根节点是什么，我们如何获得它？

要确定根节点，我们首先需要了解信息论的一些基础知识:

  • 熵:熵是对一系列输入的不确定性的度量——输入消息的数量越不确定，确定消息是什么就需要越多的输入；例如，如果我们的输入序列总是发送相同的消息，则不存在不确定性，因此熵为零。这样的输入序列也被称为纯。然而，如果同一系列以相同的概率发送 n 种不同类型的输入，那么熵变高，接收者需要询问 log 2 n 个布尔问题来确定消息。识别一条消息所需的平均位数是发送者熵的一种度量。

  • 信息增益:确定根节点，首先需要根据提供的属性对数据集进行拆分，然后确定每个属性处的熵，每个属性处的熵与目标处的熵之差决定了每个属性的信息增益或损失。

信息增益最高的属性成为根属性。然后，我们对每个子树重复这个过程，直到没有熵。让我们用一个例子来看看这个，然后从代码开始。

对于下面的例子，我们将使用一个简单的输入和流行的数据集，根据天气情况决定是否玩游戏:

| 展望 | 温度 | 湿度 | 风 | 踢足球 | | 快活的 | 热的 | 高的 | 无力的 | 不 | | 快活的 | 热的 | 高的 | 强烈的 | 不 | | 遮蔽 | 热的 | 高的 | 无力的 | 是 | | 雨 | 温和的 | 高的 | 无力的 | 是 | | 雨 | 凉爽的 | 常态 | 无力的 | 是 | | 快活的 | 凉爽的 | 常态 | 无力的 | 是 | | 雨 | 温和的 | 常态 | 无力的 | 是 | | 快活的 | 温和的 | 常态 | 强烈的 | 是 | | 遮蔽 | 温和的 | 高的 | 强烈的 | 是 | | 遮蔽 | 热的 | 常态 | 无力的 | 是 | | 雨 | 凉爽的 | 常态 | 强烈的 | 不 | | 遮蔽 | 凉爽的 | 常态 | 强烈的 | 是 | | 快活的 | 温和的 | 高的 | 无力的 | 不 |

在前面的例子中，目标是踢足球属性。假设我们的输入源具有发送 n 条消息的能力，并且发送每条消息的概率为 P n ，那么源的熵就是概率E =-PI log2(PI)*的总和。

计算目标熵

由于踢足球(目标)属性有两种可能的输出，我们将使用目标属性的频率表(指示特定值被接收的次数)来计算熵:

收到是的概率是收到的总次数除以收到的消息总数，以此类推。

| 踢足球 | | 是 | 不 | | nine | four |

所以，目标的熵如下:

targetEntropy =  -( (9/13) log2 (9/13) ) - ( (4/13) log2 (4/13) );
targetEntropy = 0.89049164021;

计算分支熵

现在，让我们进一步细分数据集，并基于每个分支计算熵。我们这里有以下四个主要分支:

  • 观点
  • 温度
  • 湿度
  • 风

让我们首先从 Outlook 的分支开始:

| | | 玩 | | | | | | 是 | 不 | 总数 | | 观点 | 快活的 | Two | three | five | | | 遮蔽 | four | Zero | four | | | 雨 | three | one | four | | | | | | Thirteen |

为了计算分支的熵，我们将首先计算每个子分支的概率，然后将其乘以该分支的熵。然后我们将每个子分支的合成熵相加，得到该分支的总熵；然后，我们可以计算分支的信息增益:

P(上场，展望)= P(弃儿) E(4，0) + P(晴天) E(2，3) + P(下雨) E(3，1)*

=(4/13) 0+(5/13) 0.970+(4/13) 0.811*

= 0.62261538461

因此，【Outlook 分支的总信息增益=目标熵-分支熵

= 0.89049164021-0.62261538461

= 0.2678762556 或 0.27**

每个分支的最终信息增益

现在，我们可以使用其余列的两个属性的频率表来计算所有分支的熵，类似于我们对 Outlook 所做的，并获得以下结果:

对于分支湿度、，有两个可能的子分支，其结果如下:

| | | 是 | 不 | 总数 | | 湿度 | 高的 | three | three | six | | | 常态 | six | one | seven | | | | | | Thirteen |

同样，对于 Wind，分手如下:

| | | 是 | 不 | 总数 | | 风 | 无力的 | six | Two | eight | | | 强烈的 | three | Two | five | | | | | | Thirteen |

对于温度，如下所示:

| | | 是 | 不 | 总数 | | 温度 | 热的 | Two | Two | four | | | 温和的 | four | one | five | | | 凉爽的 | three | one | four | | | | | | Thirteen |

我们计算每个分支的分支熵和信息增益，下面是类似于我们对 Outlook 分支的步骤的结果:

| | 观点 | 温度 | 湿度 | 风 | | 增益 | Zero point two seven | 0.055510642 | 0.110360144 | 0.017801027 |

由于 Outlook 具有最高的信息增益，我们可以将其作为根决策节点，并根据其分支分割树，然后递归地继续该过程，直到我们获得所有的叶节点，例如熵 0。

选择根节点后，我们的输入数据从左到右如下所示:

| | 遮蔽 | 热的 | 高的 | 无力的 | 是 | | | 遮蔽 | 温和的 | 高的 | 强烈的 | 是 | | | 遮蔽 | 热的 | 常态 | 无力的 | 是 | | | 遮蔽 | 凉爽的 | 常态 | 强烈的 | 是 | | | | | | | | | | 快活的 | 热的 | 高的 | 无力的 | 不 | | 观点 | 快活的 | 热的 | 高的 | 强烈的 | 不 | | | 快活的 | 凉爽的 | 常态 | 无力的 | 是 | | | 快活的 | 温和的 | 常态 | 强烈的 | 是 | | | 快活的 | 温和的 | 高的 | 无力的 | 不 | | | | | | | | | | 雨 | 温和的 | 高的 | 无力的 | 是 | | | 雨 | 凉爽的 | 常态 | 无力的 | 是 | | | 雨 | 温和的 | 常态 | 无力的 | 是 | | | 雨 | 凉爽的 | 常态 | 强烈的 | 不 |

现在，我们可以看到分支“阴”总是产生响应是(最右边一列)，所以我们可以不考虑该分支，因为熵总是 0，也就是说，节点“阴”是一个叶节点。

现在，在分支 Outlook -> Sunny，我们将需要通过重复类似于根的过程来确定下一个决策节点。基本上，我们之前做的步骤将递归地继续，直到我们确定所有的叶节点。让我们把它翻译成我们的信用卡例子的代码，并看看它的实际应用。

编码 ID3 算法

首先，我们需要一个应用；让我们继续创建一个 Angular 应用，如前所示。

从前面的例子中，我们已经看到，我们首先需要列出我们的训练数据，这些数据将被输入到我们的算法中。在这种情况下，我们将需要首先识别影响我们的目标属性(已批准)的不同属性。在不太深入的情况下，以下是主要因素(及其可能的价值)，我们将这些因素作为某件事的例子，这些因素会影响您的批准机会:

  • 信用分数:你的信用总分数(优秀、良好、一般和差)
  • 信用年龄:以年为单位的信用历史年龄(> 10，> 5，> 2，> =1)
  • 贬义言论:如果你的账号上有任何言论(0，1，2，> =3)
  • 利用率:您使用了多少批准的信用额度(高、中和低)
  • 硬查询:你最近开了多少新账户(0，1，2，> =3)

由于前面列表的组合数量是固定的，理论上，我们可以生成一个包含所有场景的数据集，然后我们可以使用该数据集 100%准确地进行预测，但是这有什么乐趣呢？相反，我们将只获取生成的数据集的一半，并使用它来预测另一半的结果。

生成训练数据集

虽然生成训练数据集可以手动完成，但这并不有趣。因此，让我们编写一个小脚本，它将帮助我们创建数据集:

// input attributes and the target values

var _ = require('lodash');

var creditScore = ['Excellent', 'Good', 'Average', 'Poor'];
var creditAge = ['>10', '>5', '>2', '>=1'];
var remarks = ['0', '1', '2', '>=3'];
var utilization = ['Low', 'Medium', 'High'];
var hardInquiries = ['0', '1', '2', '>=3'];

// expected output structure
/* {
 "creditScore": "",
 "creditAge": "",
 "remarks": "",
 "utilization": "",
 "hardInquiries": "",
 "approval": ""
 } */

var all = [];
var even = [];
var odd = [];

// does not have to be optimal, this is a one time script
_.forEach(creditScore, function(credit) {

  // generate new object on each loop at top

  var resp = {};

  resp.creditScore = credit;

  _.forEach(creditAge, function(age) {

    resp.creditAge = age;

    _.forEach(remarks, function(remark) {

      resp.remarks = remark;

      _.forEach(utilization, function(util) {

        resp.utilization = util;

        _.forEach(hardInquiries, function(inq) {

          resp.hardInquiries = inq;

          // looping is by reference so persist a copy

          all.push(_.cloneDeep(resp));

        });
      });
    });
  });
});

for (var i = 0; i < all.length; i++) {

  // index is even
  if (i % 2 === 0) {

    // training data set
    even.push(all[i]);

  } else {

    // prediction data set (input)
    odd.push(all[i])

  }
}

// apply our fake algorithm to detect which application is approved
var trainingDataWithApprovals = applyApprovals(even);

// apply approval logic so that we know what to expect
var predictionDataWithApprovals = applyApprovals(odd);

function applyApprovals(data) {
  return _.map(data, function(d) {

    // Excellent credit score is approved, no questions asked

    if (d.creditScore === 'Excellent') {
      d.approved = 'Yes';
      return d;
    }

    // if credit score is good, then account should have a decent age
    // not very high utilization, less remarks and less inquiries

    if (d.creditScore === 'Good' &&
      (d.creditAge != '>=1') &&
      (d.remarks == '1' || d.remarks == '0') &&
      d.utilization !== 'High' &&
      (d.hardInquiries != '>=3')) {
      d.approved = 'Yes';
      return d;
    }

    // if score is average, then age should be high, no remarks, not
    very high
    // utilization and little to no inquiries.

    if (d.creditScore === 'Average' &&
      (d.creditAge == '>5' || d.creditAge == '>10') &&
      d.remarks == '0' &&
      d.utilization !== 'High' &&
      (d.hardInquiries == '1' || d.hardInquiries == '0')) {
      d.approved = 'Yes';
      return d;
    }

    // reject all others including all Poor credit scores
    d.approved = 'No';
    return d;

  });
}

console.log(trainingDataWithApprovals);
console.log(predictionDataWithApprovals);

为了运行前面的脚本，让我们在信用卡项目中创建一个小的 Node.js 项目。在项目的根目录下，从终端运行以下命令来创建项目:

// create folder for containing data
mkdir training-data

// move into the new folder
cd training-data

// create a new node project (answer the questions and hit return)
npm init

// install lodash to use helper methods
npm install lodash --save

// create the js file to generate data and copy paste the code above
// into this file
touch data.js

// run the script
node data.js

运行上面的脚本记录了trainingDataWithApprovals和predictionDataWithApprovals 。

接下来，将trainingDataWithApprovals复制到如下路径的文件中:src/utils/training-data/credit-card.ts 。从前面的代码记录的数据记录数据，下面的截图中可以看到一个例子:

我们现在可以将predictionDataWithApprovals移动到app.component.ts文件中，并将approved属性重命名为expected，因为这就是我们期望的输出。我们稍后将实际输出与此进行比较:

现在我们已经准备好了训练数据并将其导入到项目中，让我们创建其余的算法来完成树。

生成决策树

为了将代码复杂度保持在最低，我们将提取所有递归调用的辅助方法，如前面的例子所示。我们可以从train()方法开始，因为它将首先被调用来确定根决策节点。

在此之前，让我们在utils文件夹中为我们的 ID3 算法创建一个可注射服务，我们将在希望使用它的地方注射该服务。这个逻辑可以存在于任何你想要的地方，服务器端或者客户端。需要注意的一点是，在这种情况下，数据集相对较小，因此在客户端训练数据集和预测结果是一件不错的事情。对于较大的数据集，训练时间要长得多，建议在服务器端这样做，如下所示:

import {Injectable} from "@angular/core";

@Injectable()
export class ID3 {

    constructor() {

    }

}

在算法的每一步，我们将严重依赖助手方法来保持实现细节的清晰；其中大部分将由lodash提供，所以让我们安装并导入它，以便实现train()方法:

npm install lodash --save

一旦安装了lodash，我们可以从train()方法开始，该方法接受三个参数:训练数据集、目标属性以及从训练数据集中提取的所有属性的列表无目标:

import {Injectable} from "@angular/core";
import { } from "lodash";

@Injectable()
export class ID3 {

    constructor() {

    }

    public train(trainingData, target, attributes) {

    }

}

要使用该服务，在主模块中将其标记为provider，然后将其注入app.component:

...
import { ID3 } from '../utils/id3';
...

@NgModule({
   ...
    providers: [
        ID3
    ],
    ...
})
export class AppModule { }

然后，为了在主组件中消费它，我们可以只导入我们刚刚创建的 ID3 服务，然后在服务实例上调用train()方法:

import { Component, OnInit } from '@angular/core';
import {ID3} from "../utils/id3";
import {without, keys, filter} from "lodash";
import {CreditCard} from "../utils/training-data/credit-card";

@Component({
    selector: 'app-root',
    templateUrl: './app.component.html',
    styleUrls: ['./app.component.scss']
})
export class AppComponent implements OnInit {
    tree;
    tests: any;

    constructor(private id3: ID3) {
        this.tree = this.id3.train(
                         CreditCard.data,
                         'approved', 
                         without(keys(CreditCard.data[0]),
                         'approved'));
    }

    ngOnInit() {
        this.tests = ... // testing data
    }

}

让我们也给我们的页面添加一些样式，让它看起来更漂亮，所以更新app.component.scss文件:

.split {
    width: 50%;
    float: left
}

table, td, th {
  text-align: center;
  border: 1px solid black;
}

table {
  border-collapse: collapse;
  width: 100%;
}

th {
  height: 50px;
}

.true {
  background: #bcf9bc;
}

.false {
  background: #ffa2a7;
}

正如前面的算法所讨论的，我们在应用中要做的第一件事是确定根决策节点，例如，具有最高信息增益的属性:

import {Injectable} from "@angular/core";
import { maxBy, uniq, map, filter, without, keys, size, chain, find, countBy } from "lodash";

@Injectable()
export class ID3 {

    constructor() {

    }

    public train(trainingData, target, attributes) {

        // calculate root node from current list of attributes
        var currentRootNode = this.getCurrentRootNode(
                                    trainingData, target, attributes);

    }

    private getCurrentRootNode(trainingData, target, attributes) {

        // get max extropy attribute
        return maxBy(attributes, (attr) => {

            // calculate information gain at each attribute
            // e.g. 'creditScore', 'creditAge' etc
            return this.gain(trainingData, target, attr);
        });
    }

    private gain(trainingData, target, attr) {
        // calculate target branches entropy e.g. approved
        var targetEntropy = this.entropy(map(trainingData, target));

        // calculate the summation of all branches entropy
        var sumOfBranchEntropies =
            chain(trainingData)

                // extract branches for the given attribute
                // e.g creditScore has the branches Excellent, Good,
                // Average, Poor
                .map(attr)

                // make the values unique
                .uniq()

                // for each unique branch calculate the branch entropy
                // e.g. calculate entropy of Excellent, Good, Average,
                Poor
                .map((branch) => {

                    // extract only the subset training data
                    // which belongs to current branch
                    var branchTrainingData = filter(trainingData, 
                    [attr, branch]);

                    // return (probability of branch) * entropy of
                    branch
                    return (branchTrainingData.length /
                    trainingData.length)
                        * this.entropy(map(branchTrainingData,
                        target));
                })

                // add all branch entropies
                // e.g. add entropy of Excellent, Good, Average, Poor
                .reduce(this.genericReducer, 0)

                // return the final value
                .valueOf();

        // return information gain
        return targetEntropy - sumOfBranchEntropies;
    }

    private entropy(vals) {

        // take all values
        return chain(vals)

            // make them unique
            // e.g. an array of Yes and No
            .uniq()

            // calculate probability of each
            .map((x) => this.probability(x, vals))

            // calculate entropy
            .map((p) => -p * Math.log2(p))

            // reduce the value
            .reduce(this.genericReducer, 0)

            // return value
            .valueOf();
    }

    private probability(val, vals){

        // calculate total number of instances
        // e.g. Yes is 100 out of the 300 values
        var instances = filter(vals, (x) => x === val).length;

        // total values passed e.g. 300
        var total = vals.length;

        // return 1/3
        return instances/total;
    }

    private genericReducer(a, b) {

        // add and return
        return a + b;
    }

从前面的代码中可以看到，我们首先通过计算每个属性的分支熵来计算树的根决策节点，并确定最大信息增益。

现在我们有了根，我们可以递归地对节点的每个分支重复这个过程，然后继续寻找决策节点，直到我们达到熵为 0，也就是叶节点。

这将我们的train()方法修改如下:

public train(trainingData, target, attributes) {
    // extract all targets from data set e.g.
    // Yes or No
    var allTargets = uniq(map(trainingData, target));

    // only Yes or No is remaining e.g. leaf node found
    if (allTargets.length == 1){
        return { leaf: true, value: allTargets[0] };
    }

    // calculate root node from current list of attributes
    var currentRootNode = this.getCurrentRootNode(
                                trainingData, target, attributes);

    // form node for current root
    var node: any = { name: currentRootNode, leaf: false };

    // remove currentRootNode from list of all attributes
    // e.g. remove creditScore or whatever the root node was
    // from the entire list of attributes
    var remainingAttributes = without(attributes, currentRootNode);

    // get unique branch names for currentRootNode
    // e.g creditScore has the branches Excellent, Good,
    // Average, Poor
    var branches = uniq(map(trainingData, currentRootNode));

    // recursively repeat the process for each branch
    node.branches = map(branches, (branch) => {

        // take each branch training data
        // e.g. training data where creditScore is Excellent
        var branchTrainingData = filter(trainingData, [currentRootNode,
        branch]);

        // create node for each branch
        var branch: any = { name: branch, leaf: false };

        // initialize branches for node
        branch.branches = [];

        // train and push data to subbranch
        branch.branches.push(this.train(
                   branchTrainingData, target, remainingAttributes));

        // return branch as a child of parent node
        return branch;
    });

    return node;
}

说完后，train()方法:

  1. 获取输入训练数据、目标属性和属性列表。
  2. 通过计算属性的每个分支的最大信息增益来获取当前根属性，并创建树的根节点。
  3. 将递归生成的子树推入根节点的分支。

预测样本输入的结果

现在我们的树已经准备好并返回，我们可以在我们的app.component中使用这个来使用predict()方法确定预测是否与预期结果相匹配:

public predict(tree, input) {
    var node = tree;

    // loop over the entire tree
    while(!node[0].leaf){

        // take node name e.g. creditScore
        var name = node[0].name;

        // take value from input sample
        var inputValue = input[name];

        // check if branches for given input exist
        var childNode = filter(node[0].branches, ['name', inputValue]);

        // if branches exist return branches or default to No
        node = childNode.length ?
            childNode[0].branches : [{ leaf: true, value: 'No'}];
    }

    // return final leaf value
    return node[0].value;
}

然后，在app.component中，我们消耗predict()方法:

...

    accuracyPct: any;

    ngOnInit() {

        this.tests = // test data set;

        this.tests.forEach((test) => {
            test.actual = this.id3.predict([this.tree], test);
            test.accurate = test.expected === test.actual;
        });

        this.accuracyPct =  (filter(this.tests, { accurate: true }).length / 
                                this.tests.length)*100;
    }

}

树和输出的可视化

虽然我们已经基于训练集生成了输入数据集的树和预期/实际结果，但是现在很难可视化这些数据。为此，让我们创建一个小组件，它接受树并在用户界面上呈现树的嵌套格式。这是非常少的，只是为了理解我们的决策树形式的数据。

在utils文件夹下，让我们首先创建名为treeview的文件夹来包含我们的组件。让我们称之为treeview，因为我们创建了组件并将其注入主模块。

对于treeview，我们首先创建treeview.ts文件:

import {Component, Input} from '@angular/core';

@Component ({
    selector: 'tree-view',
    templateUrl:'./treeview.html',
    styleUrls: ['./treeview.scss']
})
export class TreeView {
    @Input() data;
}

然后，我们将创建与组件配套的模板，并将其添加为treeview.html:

<ul *ngFor="let node of data">
    <li *ngIf="node.name">

        <!-- show name when available -->
        <span class="name">{{node.name}}</span>
    </li>
    <!-- is not root node, render branches recursively -->
    <tree-view *ngIf="!node.leaf" [data]="node.branches"></tree-view>

    <!-- if leaf node render node value -->
    <li *ngIf="node.leaf">
        <span class="leaf {{node.value}}">{{node.value}}</span>
    </li>
</ul>

让我们对treeview进行样式化，使其更加易读，treeview.scss:

ul {
  list-style: none;
  line-height: 40px;
  position: relative;

  &::before{
    content: "";
    height: calc(100% - 60px);
    display: block;
    top: 40px;
    left: 60px;
    border-left: 1px solid #333;
    position: absolute;
  }
}

li {
  position: relative;

  &::before{
    content: "";
    width: 20px;
    display: block;
    top: 50%;
    left: -20px;
    border-bottom: 1px solid #333;
    position: absolute;
    transform: translateY(-50%);
  }
}

.name {
  padding: 10px;
  background: #e1f4ff;
}

.leaf {
  padding: 10px;
  position: relative;

  &.Yes {
    background: #bcf9bc;
  }

  &.No {
    background: #ffa2a7;
  }
}

现在，为了使用treeview组件，让我们将其添加到app.module.ts中的声明中:

...
import {TreeView} from "../utils/treeview/treeview";

@NgModule({
    declarations: [
        ...
        TreeView
    ],
   ...
})
export class AppModule { }

要使用它，我们只需要将我们在app.component中生成的树绑定到tree-view组件:

添加treeview后，app.component.html更新如下:

<div *ngIf="tree">
    <tree-view [data]="[tree]"></tree-view>
</div>

这将按照预期在用户界面上呈现树:

然而，这只是生成的大树的一部分，很难阅读和可视化。让我们通过将训练和测试数据改为足球数据来尝试足球示例，我们在前面的章节中已经看到了这一点:

让我们呈现输入数据，我们传递了这些数据来测试我们的决策树。为此，我们可以修改我们的app.component.html 来同时显示表格和可视化:

<div class="split">
    <div *ngIf="tree">
        <tree-view [data]="[tree]"></tree-view>
    </div>
</div>
<div class="split">
    <h3>Overall accuracy {{accuracyPct | number}}%</h3>

    <table>
        <thead>
            <th>Credit Score</th>
            <th>Credit Age</th>
            <th>Remarks</th>
            <th>Utilization</th>
            <th>Hard Inquiries</th>
            <th>Expected</th>
            <th>Actual</th>
            <th>Accurate</th>
        </thead>
        <tbody>
            <tr *ngFor="let test of tests">
                <td>{{test.creditScore}}</td>
                <td>{{test.creditAge}}</td>
                <td>{{test.remarks}}</td>
                <td>{{test.utilization}}</td>
                <td>{{test.hardInquiries}}</td>
                <td>{{test.expected}}</td>
                <td>{{test.actual}}</td>
                <td [class]="test.accurate">{{test.accurate}}</td>
            </tr>
        </tbody>
    </table>
</div>

要设置表格的样式，我们可以将以下内容添加到我们的app.component.scss文件中:

.split {
    width: 50%;
    float: left
}

table, td, th {
  text-align: center;
  border: 1px solid black;
}

table {
  border-collapse: collapse;
  width: 100%;
}

th {
  height: 50px;
}

.true {
  background: #bcf9bc;
}

.false {
  background: #ffa2a7;
}

预期产出如下:

以足球为例:

摘要

在这一章中，我们采用了一种相当正统的方法来将树理解为数据结构，在这种方法中，我们偏离了学习树并实现其方法的标准过程。相反，我们采用了一些真实的例子，并根据手头的用例，按照我们认为合适的方式实现了这些树。在这种情况下，您将获得数据，并被要求以通用方式实现数据以扩展用例。在下一章中，我们将扩展这种方法，并使其更进一步，我们将注意到它是如何扩展到图论的。**

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/279.html