How to make a decision tree in javascript

This time I will bring you javascriptHow to make a decision tree, and what are the precautions for making a decision tree using javascript. The following is a practical case, let's take a look.

Decision tree algorithm code implementation

1. Prepare test data

Here I assume that there is a young lady in the company meeting on a blind date as an example

The following is the result of having met or been Eliminated data (part of the data was generated using mock.js):

var data =
        [
            { "姓名": "余夏", "年龄": 29, "长相": "帅", "体型": "瘦", "收入": "高", 见面: "见" },
            { "姓名": "豆豆", "年龄": 25, "长相": "帅", "体型": "瘦", "收入": "高", 见面: "见" },
            { "姓名": "帅常荣", "年龄": 26, "长相": "帅", "体型": "胖", "收入": "高", 见面: "见" },
            { "姓名": "王涛", "年龄": 22, "长相": "帅", "体型": "瘦", "收入": "高", 见面: "见" },
            { "姓名": "李东", "年龄": 23, "长相": "帅", "体型": "瘦", "收入": "高", 见面: "见" },
            { "姓名": "王五五", "年龄": 23, "长相": "帅", "体型": "瘦", "收入": "低", 见面: "见" },
            { "姓名": "王小涛", "年龄": 22, "长相": "帅", "体型": "瘦", "收入": "低", 见面: "见" },
            { "姓名": "李缤", "年龄": 21, "长相": "帅", "体型": "胖", "收入": "高", 见面: "见" },
            { "姓名": "刘明", "年龄": 21, "长相": "帅", "体型": "胖", "收入": "低", 见面: "不见" },
            { "姓名": "红鹤", "年龄": 21, "长相": "不帅", "体型": "胖", "收入": "高", 见面: "不见" },
            { "姓名": "李理", "年龄": 32, "长相": "帅", "体型": "瘦", "收入": "高", 见面: "不见" },
            { "姓名": "周州", "年龄": 31, "长相": "帅", "体型": "瘦", "收入": "高", 见面: "不见" },
            { "姓名": "李乐", "年龄": 27, "长相": "不帅", "体型": "胖", "收入": "高", 见面: "不见" },
            { "姓名": "韩明", "年龄": 24, "长相": "不帅", "体型": "瘦", "收入": "高", 见面: "不见" },
            { "姓名": "小吕", "年龄": 28, "长相": "帅", "体型": "瘦", "收入": "低", 见面: "不见" },
            { "姓名": "李四", "年龄": 25, "长相": "帅", "体型": "瘦", "收入": "低", 见面: "不见" },
            { "姓名": "王鹏", "年龄": 30, "长相": "帅", "体型": "瘦", "收入": "低", 见面: "不见" },
        ];

2. Build the basic function of the decision tree

Code:

function DecisionTree(config) {    if (typeof config == "object" && !Array.isArray(config)) this.training(config);
};
DecisionTree.prototype = {    //分割函数
    _predicates: {},    //统计属性值在数据集中的次数
    countUniqueValues(items, attr) {},    //获取对象中值最大的Key  假设 counter={a:9,b:2} 得到 "a" 
    getMaxKey(counter) {},    //寻找最频繁的特定属性值
    mostFrequentValue(items, attr) {},    //根据属性切割数据集 
    split(items, attr, predicate, pivot) {},    //计算熵
    entropy(items, attr) {},    //生成决策树
    buildDecisionTree(config) {},    //初始化生成决策树
    training(config) {},    //预测 测试
    predict(data) {},
};var decisionTree = new DecisionTree();

3. Implement the function

Because some functions are too simple, I will not explain them.

You can go to JS Simple Implementation of Decision Tree (ID3 Algorithm)_demo.html to view the complete code
It contains comments and tests for each function Method

Here I will mainly explain: the function of calculating entropy, the function of generating decision tree (information gain), and the implementation of the prediction function

The calculation of entropy and information is explained in the ID3 algorithm wiki The formula of gain

3.1. Calculate entropy (entropy) function

We can know that to calculate H(S) (that is, entropy), we need to get p(x)=x/total quantity and then calculate Just add up

Code:

//......略//统计属性值在数据集中的次数countUniqueValues(items, attr) {    var counter = {}; // 获取不同的结果值 与出现次数
    for (var i of items) {        if (!counter[i[attr]]) counter[i[attr]] = 0;
        counter[i[attr]] += 1;
    }    return counter;
},//......略//计算熵entropy(items, attr) {    var counter = this.countUniqueValues(items, attr); //计算值的出现数
    var p, entropy = 0; //H(S)=entropy=∑(P(Xi)(log2(P(Xi))))
    for (var i in counter) {
        p = counter[i] / items.length; //P(Xi)概率值
        entropy += -p * Math.log2(p); //entropy+=-(P(Xi)(log2(P(Xi))))
    }    return entropy;
},//......略var decisionTree = new DecisionTree();console.log("函数 countUniqueValues 测试:");console.log("   长相", decisionTree.countUniqueValues(data, "长相")); //测试console.log("   年龄", decisionTree.countUniqueValues(data, "年龄")); //测试console.log("   收入", decisionTree.countUniqueValues(data, "收入")); //测试console.log("函数 entropy 测试:");console.log("   长相", decisionTree.entropy(data, "长相")); //测试console.log("   年龄", decisionTree.entropy(data, "年龄")); //测试console.log("   收入", decisionTree.entropy(data, "收入")); //测试

3.2. Information gain

Formula

According to the formula we know that to get the value of information gain we need to get:

H(S) training set entropy

p(t) branch element proportion

H(t) branch data set entropy

We will divide t first match (suitable) and on match (unsuitable), so H(t):

H(match) The entropy of the suitable data set after splitting

H(on match) after splitting Entropy of inappropriate data set

So the information gain G=H(S)-(p(match)H(match)+p(on match)H(on match))

Because p( match)=number of matches/total number of items in the data set
Information gainG=H(S)-((number of matches)xH(match)+(number of on match)xH(on match))/total number of items in the data set

//......略buildDecisionTree(config){    var trainingSet = config.trainingSet;//训练集 
    var categoryAttr = config.categoryAttr;//用于区分的类别属性
    //......略
    //初始计算 训练集的熵
    var initialEntropy = this.entropy(trainingSet, categoryAttr);//<===H(S)
    //......略
    var alreadyChecked = [];//标识已经计算过了
    var bestSplit = { gain: 0 };//储存当前最佳的分割节点数据信息
    //遍历数据集
    for (var item of trainingSet) {        // 遍历项中的所有属性
        for (var attr in item) {            //跳过区分属性与忽略属性
            if ((attr == categoryAttr) || (ignoredAttributes.indexOf(attr) >= 0)) continue;            var pivot = item[attr];// 当前属性的值 
            var predicateName = ((typeof pivot == 'number') ? '>=' : '=='); //根据数据类型选择判断条件
            var attrPredPivot = attr + predicateName + pivot;            if (alreadyChecked.indexOf(attrPredPivot) >= 0) continue;//已经计算过则跳过
            alreadyChecked.push(attrPredPivot);//记录
            var predicate = this._predicates[predicateName];//匹配分割方式
            var currSplit = this.split(trainingSet, attr, predicate, pivot);            var matchEntropy = this.entropy(currSplit.match, categoryAttr);//  H(match) 计算分割后合适的数据集的熵
            var notMatchEntropy = this.entropy(currSplit.notMatch, categoryAttr);// H(on match) 计算分割后不合适的数据集的熵
             //计算信息增益: 
             // IG(A,S)=H(S)-(∑P(t)H(t))) 
             // t为分裂的子集match(匹配),on match(不匹配)
             // P(match)=match的长度/数据集的长度
             // P(on match)=on match的长度/数据集的长度
             var iGain = initialEntropy - ((matchEntropy * currSplit.match.length
                        + notMatchEntropy * currSplit.notMatch.length) / trainingSet.length);              //不断匹配最佳增益值对应的节点信息
              if (iGain > bestSplit.gain) {                  //......略
              }
        }
    } 
    //......递归计算分支}

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Related reading:

How to use canvas to make a useful graffiti drawing board

How to use s-xlsx to import Excel files and Export (below)

The above is the detailed content of How to make a decision tree in javascript. For more information, please follow other related articles on the PHP Chinese website!