Native Categorical Multiway-Split Decision Trees

Why only two branches?

A categorical feature can have three, five or twenty values. Yet popular libraries such as scikit-learn build binary trees, and they need categorical data to be turned into numbers first: one-hot columns or arbitrary codes. The tree you get back speaks the language of the encoding, not of the data.

The thesis starts from that question. Its answer is MixedDecisionTree, a classifier written from first principles on top of pandas and NumPy, where a categorical split creates one branch per observed value: outlook splits into sunny, overcast and rain, exactly as in the demo at the top. The goal was a tree that people can read, more than a tree that trains fast.

Hunt's algorithm, one split at a time.

The learner grows the tree recursively, in the style of ID3: at each node it measures how mixed the classes are, tries every candidate feature, and keeps the split that reduces the impurity the most.

The impurity I can be the entropy or the Gini index, both implemented:

Growth stops when a node is pure, when no feature is left, or when a pre-pruning limit kicks in: maximum depth, minimum samples to split, minimum samples per child. Every leaf gets the majority class, and categories never seen in training fall back to the overall majority.

def _get_impurity(self, attribute):    # attribute is a pd.Series: NumPy computes the class frequencies    values, counts = np.unique(attribute, return_counts=True)    impurity_values = []    if self.criterion == 'entropy':        for i in range(len(values)):            impurity_values.append(-(counts[i] / np.sum(counts)) * (np.log2(counts[i] / np.sum(counts))))        impurity_measure = np.sum(impurity_values)    elif self.criterion == 'gini':        for i in range(len(values)):            impurity_values.append((counts[i] / np.sum(counts)) ** 2)        impurity_measure = 1.0 - np.sum(impurity_values)    else:        raise Exception("Wrong criteria input, possible choices are: 'entropy' or 'gini'")    return impurity_measure

Three ways to read a number.

Categorical columns always branch natively. Numerical columns are the open design question, so the tree offers three representations and the thesis compares them:

# classic mode: every distinct training value of a numerical feature becomes a binary conditionfor feature in continuous_features:    feature_values_list = X_train[feature].values.tolist()    training_classes = np.unique(X_train[feature])    for i in range(len(training_classes)):        attribute_name = feature + " <= " + str(training_classes[i])        cond_var_list.clear()        for value in feature_values_list:            if value <= training_classes[i]:                cond_var_list.append(1.0)            else:                cond_var_list.append(0.0)        # a join instead of repeated inserts: this solved the memory problem        to_be_added_df = pd.DataFrame({attribute_name: cond_var_list})        X_train = X_train.reset_index(drop=True).join(to_be_added_df.reset_index(drop=True), how='left')    del X_train[feature]

Against scikit-learn, on ten datasets.

Both trees ran on the same ten datasets, the same stratified holdout (a third of the data for testing) and a full grid: three modes, two criteria, four bin counts and many pre-pruning settings, 2,592 configurations per model per dataset. All 51,840 results are archived in the repository with accuracy, weighted F1 and training time.

For each model, the highest holdout accuracy among all its archived configurations, selected independently, as recorded in the result files.

Readable, and just as accurate.

• Comparable accuracy. The same best accuracy on four datasets, higher on diabetes and parkinsons, within 2.5 points on three more, with similar weighted F1.
• Readable trees. A node with many outgoing branches, one per value, can be read by a person without decoding anything. The tree exports to text, condition by condition, with the gain of every split.
• The price is training time. scikit-learn trains much faster and uses less memory, which was never the goal here. Classifying a new example is just as fast: in both trees it costs one step per level of depth.

The thesis covers the theory behind it all, from decision-tree foundations and Hunt's algorithm to impurity measures, then the implementation of the three modes and the full experimental analysis.