집 >웹 프론트엔드 >JS 튜토리얼 >자바스크립트로 의사결정 트리를 만드는 방법

자바스크립트로 의사결정 트리를 만드는 방법

php中世界最好的语言원래의: 2018-03-12 15:31:413271검색

이번에는 javascript결정 트리를 만드는 방법과 javascript를 사용하여 결정 트리를 만들 때 Notes가 무엇인지 알려드리겠습니다. 실제 사례를 살펴보겠습니다.

의사결정 트리 알고리즘 코드 구현

1. 테스트 데이터 준비

여기서 소개팅으로 회사에 어떤 아가씨가 있다고 가정하겠습니다
다음은 충족되거나 제거된 데이터입니다(일부) ):

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

2. 의사결정 트리의 기본 기능을 구축합니다

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. 함수 구현하기

일부 기능은 너무 간단하므로 설명하지 않겠습니다. 그들
JS로 가서 간단하게 의사결정 트리(ID3 알고리즘)을 구현할 수 있습니다._demo.html 전체 코드 보기
각 함수에 대한 설명과 테스트 방법이 포함되어 있습니다

여기서는 주로 엔트로피를 계산하는 함수, 결정 트리 함수(정보 이득) 생성 및 예측 함수 구현

ID3 알고리즘에서 엔트로피 및 정보 이득 계산 공식은 위키

3.1에 설명되어 있습니다. 엔트로피(엔트로피) 함수 계산

우리는 H(S)(즉, 엔트로피)를 계산하려면 p(x)=x/총 수량을 구한 다음 계산해야 합니다. 그냥 축적
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에 따르면 정보 이득

공식

공식에 따르면 정보 이득의 값을 얻으려면 다음을 얻어야 합니다.

H(S) 훈련 세트 엔트로피

p(t) 가지 요소의 계정

H(t)의 엔트로피와 비교 분기 데이터 세트

우리는 먼저 match(적합)와 on match(부적합)를 나누므로 H(t):

H(match) 분할 후 적합한 데이터 집합의 엔트로피

H(on match) 분할 후 부적합한 데이터 세트의 엔트로피

그래서 정보 이득 G=H(S)-(p(일치)H(일치)+p(일치 시)H(일치 시))
왜냐하면 p(일치)=숫자이기 때문입니다 총 일치 수/데이터 세트의 총 항목 수
정보 이득 G=H(S)-((일치 수)xH(일치)+(일치 수)xH(일치))/data 집중된 항목 수

//......略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) {                  //......略
              }
        }
    } 
    //......递归计算分支}

이 기사의 사례를 읽으신 후 방법을 마스터하셨다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!