Дерево решений (ID3)

1function entropy(p: number): number {
2  return p === 0 || p === 1 ? 0 : -p * Math.log2(p) - (1 - p) * Math.log2(1 - p)
3}
4 
5function infoGain(rows: Row[], feature: number): number {
6  const total = entropy(avg(rows.map((r) => r.target)))
7  let weighted = 0
8  for (const v of [0, 1]) {
9    const subset = rows.filter((r) => r[feature] === v)
10    weighted += (subset.length / rows.length) * entropy(avg(subset.map((r) => r.target)))
11  }
12  return total - weighted // сколько неопределённости сняло разбиение
13}
14 
15function id3(rows: Row[], features: number[]): Tree {
16  const best = features
17    .map((f) => ({ f, gain: infoGain(rows, f) }))
18    .sort((a, b) => b.gain - a.gain)[0]!
19  if (best.gain === 0) return { leaf: majority(rows) }
20 
21  const yes = rows.filter((r) => r[best.f] === 1)
22  const no = rows.filter((r) => r[best.f] === 0)
23  return {
24    feature: best.f,
25    yes: id3(yes, features.filter((f) => f !== best.f)),
26    no: id3(no, features.filter((f) => f !== best.f)),
27  }
28}