Что должно храниться в узлах дерева для применения критерия похожести и как логично разделить листы на ветви?

В узлах дерева решений (например, CART или ID3) хранятся параметры разбиения: индекс признака (или его имя) и порог (для числового признака) либо набор значений (для категориального). В листьях — предсказание: для классификации это метка класса (мода), для регрессии — среднее целевой переменной. Для применения критерия похожести (меры неоднородности) при построении дерева в каждом узле дополнительно может храниться гистограмма классов (или сумма и сумма квадратов для регрессии), что ускоряет вычисление информационного выигрыша.

Логика разделения листьев на ветви (рекурсивное построение):

1. Вычисляем текущую неоднородность узла по выбранному критерию (например, Gini impurity для классификации, MSE для регрессии).
2. Перебираем все признаки. Для числового признака сортируем значения и рассматриваем пороги между соседними отсортированными значениями. Для каждого порога вычисляем взвешенную сумму неоднородностей левого и правого потомков. Выбираем порог, дающий максимальное уменьшение неоднородности (information gain).
3. Для категориального признака с k значениями перебираем все подмножества (обычно бинарное разбиение по одному значению или по группе). На практике для ускорения используют one-hot-encoding или разбиение «значение / не значение».
4. Применяем выбранное разбиение, рекурсивно строим левое и правое поддеревья.
5. Условия остановки: все объекты в узле принадлежат одному классу (или дисперсия ниже порога), число объектов меньше заданного минимума, достигнута максимальная глубина.

Пример рекурсивной функции на псевдокоде (классификация, Gini):

def build_tree(X, y, depth, max_depth, min_samples):
    if depth >= max_depth or len(y) < min_samples or impurity(y) == 0:
        return Leaf(prediction=mode(y))
    best_feature, best_threshold = None, None
    best_gain = -1
    for feature in range(X.shape[1]):
        # для числового признака — сортировка и поиск порога
        sorted_indices = np.argsort(X[:, feature])
        for i in range(1, len(y)):
            if X[sorted_indices[i], feature] == X[sorted_indices[i-1], feature]:
                continue
            threshold = (X[sorted_indices[i], feature] + X[sorted_indices[i-1], feature]) / 2
            left_indices = sorted_indices[:i]
            right_indices = sorted_indices[i:]
            gain = impurity(y) - (len(left_indices)/len(y))*impurity(y[left_indices]) - (len(right_indices)/len(y))*impurity(y[right_indices])
            if gain > best_gain:
                best_gain, best_feature, best_threshold = gain, feature, threshold
        # для категориального — перебор значений (здесь опущен)
    if best_gain <= 0:
        return Leaf(prediction=mode(y))
    left_mask = X[:, best_feature] <= best_threshold
    return Node(feature=best_feature, threshold=best_threshold,
                left=build_tree(X[left_mask], y[left_mask], depth+1, max_depth, min_samples),
                right=build_tree(X[~left_mask], y[~left_mask], depth+1, max_depth, min_samples))

На практике в промышленных реализациях (scikit-learn, XGBoost) применяют оптимизации: предварительная сортировка, кэширование гистограмм, приближённые алгоритмы с квантилями. Для уменьшения переобучения после построения выполняют обрезку (pruning) по валидационной выборке или используют минимальный порог уменьшения impurity.

Таким образом, в узлах дерева хранятся: признак и порог разбиения (плюс, опционально, статистика для ускорения). Разделение листьев на ветви — жадная процедура, максимизирующая уменьшение меры неоднородности при полном переборе порогов.