Случайные разрезы данных в задаче кластеризации: коротко
Кластеризация — штука сложная. Вроде все просто: сгруппировать похожее с похожим. Но когда данных вагон, а структура запутаннее клубка проводов за столом, стандартные методы вроде 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()И получаем график:
График 1
На этом графике можем увидеть процесс разделения данных случайной гиперплоскостью.
Синие точки представляют одну часть данных, лежащую по одну сторону гиперплоскости.
Красные точки лежат по другую сторону гиперплоскости.
Зелёная линия — это сама гиперплоскость, разделяющая данные. Ее наклон определяется случайным вектором нормали, а смещение — случайным значением в заданных пределах.
Переходим к самому интересному. Теперь создадим лес случайных разрезов и попробуем кластеризовать данные. Здесь потребуется чуть больше кода.
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()В итоге получим график:
График 2
На втором графике можно увидеть распределение «глубины» точек в дереве случайных разрезов. Глубина точки показывает, насколько далеко в иерархии дерева она оказалась, то есть сколько раз данные пришлось разрезать, чтобы изолировать эту точку. Светлые точки ближе к корню — они изолируются быстро, что может намекать на их одиночество или аномальность. Темные точки глубже в дереве — они группируются с другими и требуют больше разрезов, чтобы их отделить, что уже похоже на плотные кластеры.
Если на графике заметны явно выделенные области со схожей глубиной, это сигнал о кластеризации данных: дерево случайных разрезов «подсказало» нам, где данные тесно связаны. А вот точки, глубина которых резко отличается от соседних, могут быть признаками аномалий.
Random Cuts — хороший инструмент для работы с нелинейными, сложными и высокоразмерными данными. Он позволяет:
Выявлять аномалии: быстро изолируемые точки (малой глубины) часто указывают на одиночные, необычные значения.
Кластеризовать данные: области со схожей глубиной в дереве показывают плотные кластеры, которые трудно обнаружить стандартными методами.
Анализировать структуры данных: даже без явного предположения о форме распределения Random Cuts дают неплохую эвристику, полезную для предварительного анализа.
Метод легко адаптируется под разные задачи, работает с любыми размерами данных и предоставляет результат, который интуитивно интерпретируется.
17 декабря в Otus пройдет открытый урок «Абстракция как математический объект».
Речь пойдет о том, что такое абстракция и почему она важна в программировании. Вы узнаете, как правильно выбранные абстракции помогают упростить сложные системы и сделать код более понятным. Записаться можно по ссылке.
