Tree.cs

using Microsoft.Data.Analysis;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Markup;
using Unit4.CollectionsLib;

namespace DecisionTree
{
	internal class Tree
	{
		private DataFrame trainDf;
		private string targetCol;
		private BinNode<Dictionary<string, object>> tr;
		private int minSampleLeaf = 15;
		private int maxDepth = 10;
		private static bool DEBUG = true;
		private static void DebugLog(string msg)
		{
			if (DEBUG)
				Console.WriteLine($"[Tree DEBUG] {msg}");
		}
		public BinNode<Dictionary<string, object>> GetTree(){return this.tr;}
		public void ExportToDot(string path)
		{
			using (var writer = new StreamWriter(path))
			{
				writer.WriteLine("digraph Tree {");
				writer.WriteLine("node [shape=box, style=rounded];");
				int nodeId = 0;
				ExportNode(this.tr, writer, ref nodeId);
				writer.WriteLine("}");
			}
		}

		private int ExportNode(BinNode<Dictionary<string, object>> node, StreamWriter writer, ref int id)
		{
			int myId = id++;
			var data = node.GetValue();
			string label;
			if ((string)data["Type"] == "Leaf")
				label = $"Leaf\\nClass: {data["Label"]}";
			else if ((bool)data["IsNumeric"])
				label = $"{data["Column"]} ≤ {data["Threshold"]}";
			else
				label = $"{data["Column"]} = {data["Value"]}";
			writer.WriteLine($"{myId} [label=\"{label}\"];");
			if ((string)data["Type"] != "Leaf")
			{
				int leftId = ExportNode(node.GetLeft(), writer, ref id);
				int rightId = ExportNode(node.GetRight(), writer, ref id);
				writer.WriteLine($"{myId} -> {leftId} [label=\"no\"];");
				writer.WriteLine($"{myId} -> {rightId} [label=\"yes\"];");
			}
			return myId;
		}
		public Tree(DataFrame trainDf, string targetCol, int minSampleLeaf, int maxDepth)
		{

			DebugLog("Initializing Tree");
			DebugLog($"Rows: {trainDf.Rows.Count}, Target column: {targetCol}");

			this.trainDf = trainDf;
			this.targetCol = targetCol;
			this.minSampleLeaf = minSampleLeaf;
			this.maxDepth = maxDepth;
			this.tr = TrainTree(this.trainDf, this.trainDf.Columns[targetCol], 0);

			DebugLog("Training completed");

		}
		public Tree(DataFrame trainDf, string targetCol)
		{

			DebugLog("Initializing Tree");
			DebugLog($"Rows: {trainDf.Rows.Count}, Target column: {targetCol}");

			this.trainDf = trainDf;
			this.targetCol = targetCol;
			this.minSampleLeaf = 15;
			this.maxDepth = 10;
			this.tr = TrainTree(this.trainDf, this.trainDf.Columns[targetCol], 0);

			DebugLog("Training completed");

		}
		public DataFrame Pred(DataFrame inputDf)
		{

			DebugLog($"Prediction started | Rows: {inputDf.Rows.Count}");

			var predictions = new List<object>();
			foreach (var row in inputDf.Rows)
			{
				predictions.Add(Traverse(this.tr, row));
			}
			DataFrame output = inputDf.Clone();
			var predCol = new StringDataFrameColumn("Prediction", predictions.Select(p => p.ToString()));
			output.Columns.Add(predCol);

			DebugLog("Prediction completed");

			return output;
		}
		public object PredictRow(DataFrameRow row)
		{
			return Traverse(this.tr, row);
		}
		public object Traverse(BinNode<Dictionary<string, object>> node, DataFrameRow row)
		{
			var data = node.GetValue();

			if ((string)data["Type"] == "Leaf")
				return data["Label"];

			string col = data["Column"].ToString();
			bool isNumeric = (bool)data["IsNumeric"];

			if (isNumeric)
			{
				double threshold = (double)data["Threshold"];
				double value = Convert.ToDouble(row[col]);

				DebugLog($"Testing {col} <= {threshold} | Row value: {value}");

				return value <= threshold
					? Traverse(node.GetLeft(), row)
					: Traverse(node.GetRight(), row);
			}
			else
			{
				object splitVal = data["Value"];
				object rowVal = row[col];

				DebugLog($"Testing {col} == {splitVal} | Row value: {rowVal}");

				return rowVal.Equals(splitVal)
					? Traverse(node.GetRight(), row)
					: Traverse(node.GetLeft(), row);
			}
		}
		private BinNode<Dictionary<string, object>> TrainTree(DataFrame df, DataFrameColumn y, int currentDepth)
		{
			int rowCount = (int)df.Rows.Count;
			double gini = CalcGini(y.Cast<object>());
			if (gini == 0 || currentDepth >= this.maxDepth || rowCount < this.minSampleLeaf)
				return CreateLeaf(y);
			var potentialSplits = GetRankedPotentialSplits(df, y);
			foreach (var split in potentialSplits)
			{
				DataFrame rightDf, leftDf;

				if (split.IsNumeric)
				{
					var col = df.Columns[split.Column];

					var rightMask = col.ElementwiseGreaterThan(split.Threshold.Value);
					var leftMask = col.ElementwiseLessThanOrEqual(split.Threshold.Value);

					rightDf = df[rightMask];
					leftDf = df[leftMask];
				}
				else
				{
					var rightMask = df.Columns[split.Column].ElementwiseEquals(split.Value);
					var leftMask = df.Columns[split.Column].ElementwiseNotEquals(split.Value);

					rightDf = df[rightMask];
					leftDf = df[leftMask];
				}
				if (rightDf.Rows.Count >= this.minSampleLeaf && leftDf.Rows.Count >= this.minSampleLeaf)
				{

					DebugLog($"Depth {currentDepth}: Split on {split.Column} == {split.Value} (Gini: {split.Score:F4})");

					var nodeData = new Dictionary<string, object>
					{
						{ "Type", "Internal" },
						{ "Column", split.Column },
						{ "IsNumeric", split.IsNumeric }
					};
					if (split.IsNumeric)
						nodeData["Threshold"] = split.Threshold.Value;
					else
						nodeData["Value"] = split.Value;
					var node = new BinNode<Dictionary<string, object>>(nodeData);
					node.SetRight(TrainTree(rightDf, rightDf[y.Name], currentDepth + 1));
					node.SetLeft(TrainTree(leftDf, leftDf[y.Name], currentDepth + 1));
					return node;
				}

				DebugLog(split.IsNumeric ? $"Depth {currentDepth}: Split on {split.Column} <= {split.Threshold:F3} (Gini: {split.Score:F4})" : $"Depth {currentDepth}: Split on {split.Column} == {split.Value} (Gini: {split.Score:F4})");
			
			}

			DebugLog($"Depth {currentDepth}: No valid splits found among any features. Creating leaf.");

			return CreateLeaf(y);
		}
		private struct SplitInfo
		{
			public string Column;
			public object Value;
			public double? Threshold;
			public double Score;
			public bool IsNumeric;
		}
		private List<SplitInfo> GetRankedPotentialSplits(DataFrame df, DataFrameColumn y)
		{
			var splits = new List<SplitInfo>();

			foreach (var col in df.Columns)
			{
				if (col.Name == this.targetCol)
					continue;

				// NUMERIC
				if (col.DataType == typeof(int) ||
					col.DataType == typeof(float) ||
					col.DataType == typeof(double))
				{
					var (threshold, gini) = GetBestNumericSplit(df, y, col.Name);

					splits.Add(new SplitInfo
					{
						Column = col.Name,
						Threshold = threshold,
						Score = gini,
						IsNumeric = true
					});

					DebugLog($"Numeric split {col.Name} <= {threshold:F3} (Gini: {gini:F4})");
				}
				else
				{
					var bestValDict = GetBestSplitVal(df, y, col.Name);
					var best = bestValDict.First();

					splits.Add(new SplitInfo{Column = col.Name, Value = best.Key, Score = best.Value, IsNumeric = false});

					DebugLog($"Nominal split {col.Name} == {best.Key} (Gini: {best.Value:F4})");

				}
			}

			return splits.OrderBy(s => s.Score).ToList();
		}

		private BinNode<Dictionary<string, object>> CreateLeaf(DataFrameColumn y)
		{
			var leafData = new Dictionary<string, object> {{ "Type", "Leaf" }, { "Label", GetMajorityClass(y) }};
			return new BinNode<Dictionary<string, object>>(leafData);
		}
		public static object GetMajorityClass(DataFrameColumn y)
		{
			var counts = new Dictionary<object, int>();
			foreach (var value in y)
			{
				if (value == null) 
					continue;
				if (counts.ContainsKey(value))
					counts[value]++;
				else
					counts[value] = 1;
			}
			return counts.OrderByDescending(kv => kv.Value).First().Key;
		}
		public static Dictionary<object, double> GetBestSplitVal(DataFrame df, DataFrameColumn y, string col)
		{
			var scoreDict = new Dictionary<object, double>();
			foreach (var row in df.Rows)
			{
				object val = row[col];
				if (!scoreDict.ContainsKey(val))
					scoreDict[val] = CalcGiniForNominal(df, y, col, val);
			}
			var best = scoreDict.OrderBy(kv => kv.Value).First();
			return new Dictionary<object, double>{{ best.Key, best.Value }};
		}

		public static string GetBestSplitCol(DataFrame df, DataFrameColumn y)
		{
			if (GetBestSplitNominal(df, y).Values.Max() >= GetBestSplitNumeric(df, y).Values.Max())
				return GetBestSplitNominal(df, y).First().Key;
			return GetBestSplitNumeric(df, y).First().Key;
		}
		public static Dictionary<string, double> GetBestSplitNumeric(DataFrame df, DataFrameColumn y)
		{
			var scoreDict = new Dictionary<string, double>();
			scoreDict[""] = 0.0;
			var res = new Dictionary<string, double>();
			res[scoreDict.OrderBy(kv => kv.Value).First().Key] = scoreDict.Values.Max();
			return res;
		}
		public static double CalcGiniForNumeric(DataFrame df, DataFrameColumn y, string col)
		{
			return 0.0;
		}
		public static Dictionary<string, double> GetBestSplitNominal(DataFrame df, DataFrameColumn y)
		{
			var scoreDict = new Dictionary<string, double>();
			foreach (var col in df.Columns)
			{
				if (col.Name == y.Name)
					continue;
				if (col.DataType != typeof(string) && !col.DataType.IsEnum)
					continue;
				double best = double.MaxValue;
				foreach (var row in df.Rows)
				{
					object val = row[col.Name];
					double gini = CalcGiniForNominal(df, y, col.Name, val);
					best = Math.Min(best, gini);
				}
				scoreDict[col.Name] = best;
			}
			if (scoreDict.Count == 0)
				return new Dictionary<string, double> { { "", 1.0 } };
			var bestCol = scoreDict.OrderBy(kv => kv.Value).First();
			return new Dictionary<string, double>{{ bestCol.Key, bestCol.Value }};
		}

		public static double CalcGiniForNominal(DataFrame df, DataFrameColumn y, string col, object value)
		{
			var left = new List<object>();
			var right = new List<object>();
			for (int i = 0; i < df.Rows.Count; i++)
				if (df[col][i].Equals(value))
					right.Add(y[i]);
				else
					left.Add(y[i]);
			int n = left.Count + right.Count;
			if (left.Count == 0 || right.Count == 0)
				return double.MaxValue;
			return (left.Count / (double)n) * CalcGini(left) + (right.Count / (double)n) * CalcGini(right);
		}
		public static double CalcValProp(DataFrame df, string col, object value)
		{
			double totalC = (double)df.Rows.Count;
			int valC = 0;
			foreach (DataFrameRow row in df.Rows)
				if (row[col] == value)
					valC++;
			return valC / totalC;
		}
		public static double CalcGiniForVal(DataFrame df, DataFrameColumn y, string col, object value)
		{
			int n = (int)df.Rows.Count;
			var ySub = Enumerable.Range(0, (int)n).Where(i => df.Columns[col][i].Equals(value)).Select(i => y[i]).ToList();
			return CalcGini(ySub);
		}
		public static double CalcGini(IEnumerable<object> values)
		{
			var counts = new Dictionary<object, long>();
			int total = 0;
			foreach (var val in values)
			{
				total++;
				if (counts.ContainsKey(val))
					counts[val]++;
				else
					counts[val] = 1;
			}
			if (total == 0) return 0.0;
			double sumSquares = counts.Values.Select(c => (double)c / total).Sum(p => p * p);
			return 1.0 - sumSquares;
		}
		// Numeric
		public static double CalcGiniForNumeric(DataFrame df, DataFrameColumn y, string col, double threshold)
		{
			var left = new List<object>();
			var right = new List<object>();

			for (int i = 0; i < df.Rows.Count; i++)
				if (Convert.ToDouble(df[col][i]) <= threshold)
					left.Add(y[i]);
				else
					right.Add(y[i]);

			int n = (int)df.Rows.Count;
			int nL = left.Count;
			int nR = right.Count;

			if (nL == 0 || nR == 0)
				return double.MaxValue;

			return (nL / (double)n) * CalcGini(left) + (nR / (double)n) * CalcGini(right);
		}
		public static (double threshold, double gini) GetBestNumericSplit(DataFrame df, DataFrameColumn y, string col)
		{
			var values = new List<double>();
			for (int i = 0; i < df.Rows.Count; i++)
				if (df[col][i] != null)
					values.Add(Convert.ToDouble(df[col][i]));
			values = values.Distinct().OrderBy(v => v).ToList();
			double bestGini = double.MaxValue;
			double bestThreshold = values[0];
			for (int i = 0; i < values.Count - 1; i++)
			{
				double threshold = (values[i] + values[i + 1]) / 2.0;
				double gini = CalcGiniForNumeric(df, y, col, threshold);
				if (gini < bestGini)
				{
					bestGini = gini;
					bestThreshold = threshold;
				}
			}
			return (bestThreshold, bestGini);
		}

	}
}