Случайные разрезы данных в задаче кластеризации: коротко

Кластеризация — штука сложная. Вроде все просто: сгруппировать похожее с похожим. Но когда данных вагон, а структура запутаннее клубка проводов за столом, стандартные методы вроде 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 пройдет открытый урок «Абстракция как математический объект».

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