Кластеризация — штука сложная. Вроде все просто: сгруппировать похожее с похожим. Но когда данных вагон, а структура запутаннее клубка проводов за столом, стандартные методы вроде k‑means или DBSCAN начинают сдавать позиции. Особенно больно, если данные нелинейные, а пространство хоть на глобус натягивай.

И вот тут хорошо зайдет Random Cuts — подход, который берет все это хаосное пространство и начинает резать его случайными гиперплоскостями.

Когда мы создаем гиперплоскость, задавая ее нормаль и смещение, мы фактически вводим линейное неравенство, разделяющее пространство. Если точка находится в области с высокой плотностью (то есть много точек сосредоточено рядом), ее изоляция потребует больше разрезов, так как каждый разрез уменьшает количество соседей. Чем больше разрезов, тем «глубже» точка в структуре данных.

С другой стороны, если точка изначально находится в области с низкой плотностью (например, на периферии или в «аномальной» зоне), то уже первый или второй разрез отделяет ее. Таким образом, Random Cuts позволяют строить оценку плотности, используя концепцию глубины в дереве разрезов.

Переходим к делу

Посмотрим, как это всё работает в коде. Будем использовать Python и установим нужные библиотеки:

pip install numpy scikit-learn matplotlib

Начнем с того, чтобы понять, как сгенерировать случайную гиперплоскость. Пусть у нас есть -мерное пространство.

import numpy as np

def generate_random_hyperplane(dimensions):
    # Генерация случайного вектора нормали
    normal_vector = np.random.normal(size=dimensions)
    normal_vector /= np.linalg.norm(normal_vector)  # Нормализация
    # Генерация смещения
    offset = np.random.uniform(-1, 1)
    return normal_vector, offset

# Пример для 2D пространства
normal, offset = generate_random_hyperplane(2)
print(f"Нормаль: {normal}, Смещение: {offset}")

Теперь попробуем разделить данные. Мы сгенерируем случайные точки и посмотрим, как они делятся относительно гиперплоскости.

def split_data(points, normal, offset):
    # Вычисляем скалярное произведение для каждой точки
    distances = np.dot(points, normal) - offset
    # Разделяем данные по знаку расстояния
    left = points[distances < 0]
    right = points[distances >= 0]
    return left, right

# Генерация случайных данных
data = np.random.uniform(-5, 5, (100, 2))

# Деление данных
left, right = split_data(data, normal, offset)

# Визуализация
import matplotlib.pyplot as plt

plt.scatter(left[:, 0], left[:, 1], c='blue', label='Left')
plt.scatter(right[:, 0], right[:, 1], c='red', label='Right')
plt.axline((0, offset), slope=-normal[0]/normal[1], color='green', label='Hyperplane')
plt.legend()
plt.show()

И получаем график:

На этом графике можем увидеть процесс разделения данных случайной гиперплоскостью.

• Синие точки представляют одну часть данных, лежащую по одну сторону гиперплоскости.

• Красные точки лежат по другую сторону гиперплоскости.

• Зелёная линия — это сама гиперплоскость, разделяющая данные. Ее наклон определяется случайным вектором нормали, а смещение — случайным значением в заданных пределах.

Переходим к самому интересному. Теперь создадим лес случайных разрезов и попробуем кластеризовать данные. Здесь потребуется чуть больше кода.

class RandomCutTree:
    def __init__(self, depth=0):
        self.left = None
        self.right = None
        self.normal = None
        self.offset = None
        self.depth = depth

    def fit(self, points):
        if len(points) <= 1 or self.depth > 10:  # Ограничение по глубине
            return
        # Генерируем случайную гиперплоскость
        dimensions = points.shape[1]
        self.normal, self.offset = generate_random_hyperplane(dimensions)
        # Разделяем данные
        left_points, right_points = split_data(points, self.normal, self.offset)
        # Рекурсивное построение дерева
        self.left = RandomCutTree(self.depth + 1)
        self.right = RandomCutTree(self.depth + 1)
        self.left.fit(left_points)
        self.right.fit(right_points)

    def predict(self, point):
        if self.left is None and self.right is None:
            return self.depth  # Возвращаем глубину как "оценку"
        distance = np.dot(point, self.normal) - self.offset
        if distance < 0:
            return self.left.predict(point)
        else:
            return self.right.predict(point)

# Пример работы
tree = RandomCutTree()
tree.fit(data)

# Оценка точек
scores = [tree.predict(point) for point in data]

# Визуализация
plt.scatter(data[:, 0], data[:, 1], c=scores, cmap='viridis')
plt.colorbar(label='Depth Score')
plt.show()

В итоге получим график:

На втором графике можно увидеть распределение «глубины» точек в дереве случайных разрезов. Глубина точки показывает, насколько далеко в иерархии дерева она оказалась, то есть сколько раз данные пришлось разрезать, чтобы изолировать эту точку. Светлые точки ближе к корню — они изолируются быстро, что может намекать на их одиночество или аномальность. Темные точки глубже в дереве — они группируются с другими и требуют больше разрезов, чтобы их отделить, что уже похоже на плотные кластеры.

Если на графике заметны явно выделенные области со схожей глубиной, это сигнал о кластеризации данных: дерево случайных разрезов «подсказало» нам, где данные тесно связаны. А вот точки, глубина которых резко отличается от соседних, могут быть признаками аномалий.

Random Cuts — хороший инструмент для работы с нелинейными, сложными и высокоразмерными данными. Он позволяет:

1. Выявлять аномалии: быстро изолируемые точки (малой глубины) часто указывают на одиночные, необычные значения.

2. Кластеризовать данные: области со схожей глубиной в дереве показывают плотные кластеры, которые трудно обнаружить стандартными методами.

3. Анализировать структуры данных: даже без явного предположения о форме распределения Random Cuts дают неплохую эвристику, полезную для предварительного анализа.

Метод легко адаптируется под разные задачи, работает с любыми размерами данных и предоставляет результат, который интуитивно интерпретируется.

17 декабря в Otus пройдет открытый урок «Абстракция как математический объект».

Речь пойдет о том, что такое абстракция и почему она важна в программировании. Вы узнаете, как правильно выбранные абстракции помогают упростить сложные системы и сделать код более понятным. Записаться можно по ссылке.