outlook,temperature,humidity,windy,play
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes
rainy,mild,high,TRUE,no

// 首先做一个对数处理
double log2(num x) => log(x) / ln2;

// 针对概率序列p(p1,p2,...,pn),熵为：（用到了List类的fold方法）
double _entropy(Iterable<double> p) =>
    -p.fold(0, (prev, x) => prev + x * log2(x));

// 求一组数据各种可能发生的概率（即最后一列的概率）。用到了dart Map类的update方法。
Iterable<double> _probability(List data) {
  var map = <Object, int>{};
  for (var row in data) map.update(row.last, (v) => v + 1, ifAbsent: () => 1);
  return map.values.map((e) => e / data.length);
}

// 求一组数据的熵。
double entropy(List data) => _entropy(_probability(data));

// 根据第i列特征，对数据进行分类
Map<Object, List> classify(List data, int i) {
  var map = <Object, List>{};
  for (var row in data) {
    map.update(row[i], (v) {
      v.add(row);
      return v;
    }, ifAbsent: () => [row]);
  }
  return map;
}

// 对给定的数据data，求增益最大的特征。
// usedAttrs 为已经使用过的特征，不能重复使用;
// t 为该组数据的总的熵，避免重复计算；
int bestAttr(List data, List<int> usedAttrs, double totalEnt) {
  var gains = [
    for (var i = 0; i < data[0].length - 1; i++)
      // 注意对于已经使用过的特征，一定要给予一个负值，以确保其不会对后续的计算产生干扰
      usedAttrs.contains(i) ? -1 : gain(totalEnt, data, i)
  ];

  var best = 0, maxg = gains[0];
  for (var i = 1; i < gains.length; i++) {
    if (maxg < gains[i]) {
      maxg = gains[i];
      best = i;
    }
  }
  return best;
}

// 计算以第i列为分类的信息增益
double gain(double totalEnt, List data, int i) =>
    totalEnt - entropyByAttr(data, i);

// 计算以第i列为分类的熵
double entropyByAttr(List data, int i) {
  var ep = 0.0, groups = classify(data, i).values;
  for (var group in groups) ep += group.length / data.length * entropy(group);
  return ep;
}

// 递归创建决策树
TreeNode buildTree(List data, List<String> attrs, List<int> usedAttrs) {
  // 计算数据集的总熵
  var t = entropy(data);
  // 若总熵为0，说明已经不需要继续分类
  if (t == 0) return TreeNode(data[0].last, null, null);

  // 寻找当前信息增益最大的特征
  var i = bestAttr(data, usedAttrs, t);
  var node = TreeNode(attrs[i], [], []);
  // 注意这里一定要生成新的List，因为List是传递引用的。否则会引起多个child之间的混乱。
  var newUsed = [for (var j in usedAttrs) j, i];

  // 对新的特征进行数据分类，递归计算每个分类
  var groups = classify(data, i);
  for (var entry in groups.entries) {
    node.edges.add(entry.key);
    node.children.add(buildTree(entry.value, attrs, newUsed));
  }
  return node;
}

class TreeNode {
  String attribute; // 特征名称
  List<Object> edges; // 边，也即特征的具体属性
  List<TreeNode> children;

  TreeNode(this.attribute, this.edges, this.children);
}

// 递归打印树
void printTree(TreeNode root, int indent) {
  print(\'${\' \' * indent}特征：${root.attribute}\');
  if (root.edges == null) return;

  for (var i = 0; i < root.edges.length; i++) {
    print(\'${\' \' * (indent + 2)}属性：${root.edges[i]}\');
    printTree(root.children[i], indent + 4);
  }
}

// 加载数据，采用stream流式加载
Future<Map<String, List>> loadData(String path) async {
  var lines =
      File(path).openRead().transform(utf8.decoder).transform(LineSplitter());

  List<String> attributes;
  var data = <List>[], ln = 0;

  await for (var line in lines) {
    if (ln++ == 0) {
      attributes = line.trim().split(\',\');
    } else {
      data.add(line.trim().split(\',\'));
    }
  }

  return {\'attributes\': attributes, \'data\': data};
}

// 执行测试
Future<void> dt_run() async {
  // var info = await loadData(\'./lib/decision_tree/melon.dat\');
  var info = await loadData(\'./lib/decision_tree/golf.dat\');
  var attrs = info[\'attributes\'], data = info[\'data\'];
  var root = buildTree(data, attrs, []);
  printTree(root, 0);
}

特征：outlook
  属性：sunny
    特征：humidity
      属性：high
        特征：no
      属性：normal
        特征：yes
  属性：overcast
    特征：yes
  属性：rainy
    特征：windy
      属性：FALSE
        特征：yes
      属性：TRUE
        特征：no
Exited

色泽,根蒂,敲声,纹理,脐部,触感,好瓜
青绿,蜷缩,浊响,清晰,凹陷,硬滑,好瓜
乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,好瓜
乌黑,蜷缩,浊响,清晰,凹陷,硬滑,好瓜
青绿,蜷缩,沉闷,清晰,凹陷,硬滑,好瓜
浅白,蜷缩,浊响,清晰,凹陷,硬滑,好瓜
青绿,稍蜷,浊响,清晰,稍凹,软粘,好瓜
乌黑,稍蜷,浊响,稍糊,稍凹,软粘,好瓜
乌黑,稍蜷,浊响,清晰,稍凹,硬滑,好瓜
乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,坏瓜
青绿,硬挺,清脆,清晰,平坦,软粘,坏瓜
浅白,硬挺,清脆,模糊,平坦,硬滑,坏瓜
浅白,蜷缩,浊响,模糊,平坦,软粘,坏瓜
青绿,稍蜷,浊响,稍糊,凹陷,硬滑,坏瓜
浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,坏瓜
乌黑,稍蜷,浊响,清晰,稍凹,软粘,坏瓜
浅白,蜷缩,浊响,模糊,平坦,硬滑,坏瓜
青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,坏瓜

特征：纹理
  属性：清晰
    特征：根蒂
      属性：蜷缩
        特征：好瓜
      属性：稍蜷
        特征：色泽
          属性：青绿
            特征：好瓜
          属性：乌黑
            特征：触感
              属性：硬滑
                特征：好瓜
              属性：软粘
                特征：坏瓜
      属性：硬挺
        特征：坏瓜
  属性：稍糊
    特征：触感
      属性：软粘
        特征：好瓜
      属性：硬滑
        特征：坏瓜
  属性：模糊
    特征：坏瓜
Exited