javascript实现朴素贝叶斯分类与决策树ID3分类

const HashMap = require('./HashMap');function Bayes($data){
this._DATA = $data;
}
Bayes.prototype = {
/**
* 将训练数据单条数据按类别分类
* @return HashMap<类别，对用类别的训练数据>
*/
dataOfClass: function() {
var map = new HashMap();
var t = [], c = '';
var datas = this._DATA;
if(!(datas instanceof Array)) return;
for(var i = 0; i < datas.length; i++){
t = datas[i];
c = t[t.length - 1];
if(map.hasKey(c)){
var ot = map.get(c);
ot.push(t);
map.put(c, ot);
}else{
var nt = [];
nt.push(t);
map.put(c, nt);
}
}
return map;
},
/**
* 预测测试数据的类别
* @param Array testT 测试数据
* @return String 测试数据对应类别
*/
predictClass: function(testT){
var doc = this.dataOfClass();
var maxP = 0, maxPIndex = -1;
var classes = doc.keys();
for(var i = 0; i < classes.length; i++){
var c = classes[i]
var d = doc.get(c);
var pOfC = d.length / this._DATA.length;
for(var j = 0; j < testT.length; j++){
var pv = this.pOfV(d, testT[j], j);
pOfC = pOfC * pv;
}
if(pOfC > maxP){
maxP = pOfC;
maxPIndex = i;
}
}
if(maxPIndex === -1 || maxPIndex > doc.length){
return '无法分类';
}
return classes[maxPIndex];
},
/**
* 计算指定属性在训练数据中指定值出现的条件概率
* @param d 属于某一类的训练元组
* @param value 指定属性
* @param index 指定属性所在列
* @return 特征属性在某类别下的条件概率
*/
pOfV: function(d, value, index){
var p = 0, count = 0, total = d.length, t = [];
for(var i = 0; i < total; i++){
if(d[i][index] === value)
count++;
}
p = count / total;
return p;
}
}module.exports = Bayes;

const HashMap = require('./HashMap');
const $data = require('./data');
const TreeNode = require('./TreeNode');
const InfoGain = require('./InfoGain');function Iterator(arr){
if(!(arr instanceof Array)){
throw new Error('iterator needs a arguments that type is Array!');
}
this.arr = arr;
this.length = arr.length;
this.index = 0;
}
Iterator.prototype.current = function() {
return this.arr[this.index-1];
}
Iterator.prototype.next = function(){
this.index += 1;
if(this.index > this.length || this.arr[this.index-1] === null)
return false;
return true;
}function DecisionTree(data, attribute) {
if(!(data instanceof Array) || !(attribute instanceof Array)){
throw new Error('argument needs Array!');
}
this._data = data;
this._attr = attribute;
this._node = this.createDT(this._data,this._attr);
}
DecisionTree.prototype.createDT = function(data, attrList) {
var node = new TreeNode();
var resultMap = this.isPure(this.getTarget(data)); if(resultMap.size() === 1){
node.setType('result');
node.setName(resultMap.keys()[0]);
node.setVals(resultMap.keys()[0]);
// console.log('单节点树：' + node.getVals());
return node;
}
if(attrList.length === 0){
var max = this.getMaxVal(resultMap);
node.setType('result');
node.setName(max)
node.setVals(max);
// console.log('最普遍性结果：'+ max);
return node;
} var maxGain = this.getMaxGain(data, attrList).maxGain;
var attrIndex = this.getMaxGain(data, attrList).attrIndex
// console.log('选出的最大增益率属性为：'+ attrList[attrIndex]);
// console.log('创建节点：'+attrList[attrIndex])
node.setName(attrList[attrIndex]);
node.setType('attribute'); var remainAttr = new Array();
remainAttr = attrList;
// remainAttr.splice(attrIndex, 1); var self = this;
var gain = new InfoGain(data, attrList)
var attrValueMap = gain.getAttrValue(attrIndex); //最好分类的属性的值MAP
var possibleValues = attrValueMap.keys(); node_vals = possibleValues.map(function(v) {
// console.log('创建分支：'+v);
var newData = data.filter(function(x) {
return x[attrIndex] === v;
});
// newData = newData.map(function(v) {
// return v.slice(1);
// })
var child_node = new TreeNode(v, 'feature_values');
var leafNode = self.createDT(newData, remainAttr);
child_node.setVals(leafNode);
return child_node;
})
node.setVals(node_vals); this._node = node;
return node;
}
/**
* 判断训练数据纯度分类是否为一种分类或没有分类
*/
DecisionTree.prototype.getTarget = function(data){
var list = new Array();
var iter = new Iterator(data);
while(iter.next()){
var index = iter.current().length - 1;
var value = iter.current()[index];
list.push(value);
}
return list;
},
/**
* 获取分类结果数组，判断纯度
*/
DecisionTree.prototype.isPure = function(list) {
var map = new HashMap(), count = 1;
list.forEach(function(item) {
if(map.get(item)){
count++;
}
map.put(item, count);
});
return map;
}
/**
* 获取最大增益量属性
*/
DecisionTree.prototype.getMaxGain = function(data, attrList) {
var gain = new InfoGain(data, attrList);
var maxGain = 0;
var attrIndex = -1;
for(var i = 0; i < attrList.length; i++){
var temp = gain.getGainRaito(i);
if(maxGain < temp){
maxGain = temp;
attrIndex = i;
}
}
return {attrIndex: attrIndex, maxGain: maxGain};
}
/**
* 获取resultMap中值最大的key
*/
DecisionTree.prototype.getMaxVal = function(map){
var obj = map.obj, temp = 0, okey = '';
for(var key in obj){
if(temp < obj[key] && typeof obj[key] === 'number'){
temp = obj[key];
okey = key;
};
}
return okey;
}
/**
* 预测属性
*/
DecisionTree.prototype.predictClass = function(sample){
var root = this._node;
var map = new HashMap();
var attrList = this._attr;
for(var i = 0; i < attrList.length; i++){
map.put(attrList[i], sample[i]);
} while(root.type !== 'result'){
if(root.name === undefined){
return root = '无法分类';
}
var attr = root.name;
var sample = map.get(attr);
var childNode = root.vals.filter(function(node) {
return node.name === sample;
});
if(childNode.length === 0){
return root = '无法分类';
}
root = childNode[0].vals; // 只遍历attribute节点
}
return root.vals;
}module.exports = DecisionTree;

const HashMap = require('./HashMap');function Iterator(arr){
if(!(arr instanceof Array)){
throw new Error('iterator needs a arguments that type is Array!');
}
this.arr = arr;
this.length = arr.length;
this.index = 0;
}
Iterator.prototype.current = function() {
return this.arr[this.index-1];
}
Iterator.prototype.next = function(){
this.index += 1;
if(this.index > this.length || this.arr[this.index-1] === null)
return false;
return true;
}/**
* 计算信息增益类
* @param Array data 训练数据集
* @param Array data 作用的特征属性
*/
function InfoGain(data, attr) {
if(!(data instanceof Array) || !(attr instanceof Array)){
throw new Error('arguments needs Array!');
}
this._data = data;
this._attr = attr;
}
InfoGain.prototype = {
/**
* 获取训练数据分类个数
* @return hashMap<类别, 该类别数量>
*/
getTargetValue: function() {
var map = new HashMap();
var iter = new Iterator(this._data);
while(iter.next()){
var t = iter.current();
var key = t[t.length-1];
var value = map.get(key);
map.put(key, value !== undefined ? ++value : 1);
}
return map;
},
/**
* 获取训练数据信息熵
* @return 训练数据信息熵
*/
getEntroy: function(){
var targetValueMap = this.getTargetValue();
var targetKey = targetValueMap.keys(), entroy = 0;
var self = this;
var iter = new Iterator(targetKey);
while(iter.next()){
var p = targetValueMap.get(iter.current()) / self._data.length;
entroy += (-1) * p * (Math.log(p) / Math.LN2);
}
return entroy;
},
/**
* 获取属性值在训练数据集中的数量
* @param number index 属性名数组索引
*/
getAttrValue: function(index){
var map = new HashMap();
var iter = new Iterator(this._data);
while(iter.next()){
var t = iter.current();
var key = t[index];
var value = map.get(key);
map.put(key, value !== undefined ? ++value : 1);
}
return map;
},
/**
* 得到属性值在决策空间的比例
* @param string name 属性值
* @param number index 属性所在第几列
*/
getAttrValueTargetValue: function(name, index){
var map = new HashMap();
var iter = new Iterator(this._data);
while(iter.next()){
var t = iter.current();
if(name === t[index]){
var size = t.length;
var key = t[t.length-1];
var value = map.get(key);
map.put(key, value !== undefined ? ++value : 1);
}
}
return map;
},
/**
* 获取特征属性作用于训练数据集后分类出的数据集的熵
* @param number index 属性名数组索引
*/
getInfoAttr: function(index){
var attrValueMap = this.getAttrValue(index);
var infoA = 0;
var c = attrValueMap.keys();
for(var i = 0; i < attrValueMap.size(); i++){
var size = this._data.length;
var attrP = attrValueMap.get(c[i]) / size;
var targetValueMap = this.getAttrValueTargetValue(c[i], index);
var totalCount = 0 ,valueSum = 0;
for(var j = 0; j < targetValueMap.size(); j++){
totalCount += targetValueMap.get(targetValueMap.keys()[j]);
}
for(var k = 0; k < targetValueMap.size(); k++){
var p = targetValueMap.get(targetValueMap.keys()[k]) / totalCount;
valueSum += (Math.log(p) / Math.LN2) * p;
}
infoA += (-1) * attrP * valueSum;
}
return infoA;
},
/**
* 获得信息增益量
*/
getGain: function(index) {
return this.getEntroy() - this.getInfoAttr(index);
},
getSplitInfo: function(index){
var map = this.getAttrValue(index);
var splitA = 0;
for(var i = 0; i < map.size(); i++){
var size = this._data.length;
var attrP = map.get(map.keys()[i]) / size;
splitA += (-1) * attrP * (Math.log(attrP) / Math.LN2);
}
return splitA;
},
/**
* 获得增益率
*/
getGainRaito: function(index){
return this.getGain(index) / this.getSplitInfo(index);
},
getData4Value: function(attrValue, attrIndex){
var resultData = new Array();
var iter = new Iterator(this._data);
while(iter.next()){
var temp = iter.current();
if(temp[attrIndex] === attrValue){
resultData.push(temp);
}
}
return resultData;
}
}
// var gain = new InfoGain($data, ['sunny']);// console.log(gain.getGainRaito(0), gain.getGainRaito(1),gain.getGainRaito(2),gain.getGainRaito(3))
// console.log(gain.getGain(0),gain.getGain(1),gain.getGain(2),gain.getGain(3))
module.exports = InfoGain;