Optimal Gini Split Finder for Binary Classification Trees

Decision trees are powerful and interpretable machine learning models that recursively partition the feature space into regions that are as homogeneous as possible with respect to the target variable. At the heart of this partitioning process lies the split selection algorithm—the mechanism that determines which feature and threshold combination will best separate the data at each node.

The Gini impurity is one of the most widely used criteria for evaluating the quality of a split in classification trees. For a binary classification problem, the Gini impurity measures how often a randomly chosen element from a set would be incorrectly classified if it were randomly labeled according to the distribution of labels in the subset. A Gini impurity of 0 indicates a perfectly pure node where all samples belong to a single class.

For a node with n samples, where p₁ is the proportion of class 1 samples, the Gini impurity is calculated as:

$$Gini = 1 - p_0^2 - p_1^2 = 2 \cdot p_0 \cdot p_1$$

When evaluating a potential split, we compute the weighted Gini impurity by taking the weighted average of the Gini impurities of the two resulting child nodes, where weights are proportional to the number of samples in each child:

$$Gini_{weighted} = \frac{n_{left}}{n} \cdot Gini_{left} + \frac{n_{right}}{n} \cdot Gini_{right}$$

Your Task: Implement a function that exhaustively searches through all possible feature-threshold combinations in a dataset and identifies the split that yields the minimum weighted Gini impurity. The function should:

• Evaluate every unique feature value as a potential threshold for splitting
• A sample goes to the left child if its feature value is ≤ threshold, otherwise to the right child
• Return the (feature_index, threshold) pair that produces the lowest weighted Gini impurity
• In case of ties (multiple splits achieving the same minimum impurity), return the first encountered split when scanning features in order and thresholds in sorted order within each feature