Как можно пересчитать метки AgglomerativeClustering?

Содержание

Вопрос или проблема
Ответ или решение
1. Использование compute_full_tree
2. Изменение порога расстояния
3. Реализация функции для переоценки меток
4. Пояснение функции
Заключение

Вопрос или проблема

Я использую AgglomerativeClustering из scikit-learn на большом наборе данных.

Я хотел бы изменить distance_threshold после того, как модель уже была вычислена. Вычисление модели выполняется медленно (квадратичное время), но переобчисление меток для нового distance_threshold должно выполняться легко за линейное время, так как модель сохраняет массивы children_ и distances_ постоянно. Но как можно переобчислить метки для другого distance_threshold?

Можно предположить, что изначально distance_threshold был установлен на 0, то есть всё дерево было вычислено.

Один из вариантов ускорения вычислений с различными порогами – это кэширование результатов с помощью опции memory.

Что-то вроде этого:

from sklearn.cluster import AgglomerativeClustering

clustering = AgglomerativeClustering(compute_full_tree=True,
                                     distance_threshold=1.0,
                                     memory='mycachedir', 
                                     n_clusters=None,)

Вы можете вычислить новую метку, используя children_ и distances_ рекурсивно, следуя приведенному ниже определению из документации scikit-learn.

children_array-like формы (n_samples-1, 2)

Дети каждого узла, не являющегося листом. Значения меньше n_samples соответствуют листьям дерева, которые являются оригинальными образцами. Узел i, который больше или равен n_samples, является нелистовым узлом и имеет детей children_[i – n_samples]. В альтернативном варианте на i-й итерации, children[i][0] и children[i][1] объединяются, чтобы сформировать узел n_samples + I.

distances_array-like формы (n_nodes-1,)

Расстояния между узлами в соответствующем месте в children_. Вычисляется только если используется distance_threshold или compute_distances установлено в True.

from sklearn.cluster import AgglomerativeClustering
from sklearn import datasets
iris = datasets.load_iris()
x, y = iris.data, iris.target

ac = AgglomerativeClustering(n_clusters=None, affinity='euclidean', linkage="complete", compute_full_tree=True, distance_threshold=0, )
labels = ac.fit_predict(x)

children = ac.children_
distances = ac.distances_
thres = 1.5
n_samples = 150

def get_branch(label):  # Возвращает индекс "детей" на основе узла
    for idx,child in enumerate(children):
        if label in child:
            return idx

def new_label(label):

    branch = get_branch(label)
    distance = distances[branch]
    while distance < thres:
        parent = branch + n_samples   # Согласно документации, это узел родителя
        branch = get_branch(parent)   # Получаем индекс родителя
        distance = distances[branch]  # Получаем расстояние элементов в индексе 

    return label if not parent else parent
    
new_label(100)

Ответ или решение

Чтобы переоценить метки после выполнения агломеративной кластеризации с использованием scikit-learn, вам потребуется внести изменения в значение параметра distance_threshold, не проводя повторную полную кластеризацию, так как это может быть вычислительно затратным для больших наборов данных. Сначала важно отметить, что при исходной настройке distance_threshold=0 создается полное дерево, и вы можете сохранить информацию о структуре дерева в массивы children_ и distances_.

Вот шаги, которые вам нужно выполнить для переоценки меток при изменении distance_threshold:

1. Использование `compute_full_tree`

Прежде всего, убедитесь, что вы создаете модель с параметрами n_clusters=None и compute_full_tree=True. Это позволит вам сохранить полное дерево кластеризации:

from sklearn.cluster import AgglomerativeClustering
from sklearn import datasets

# Загружаем данные
iris = datasets.load_iris()
X = iris.data

# Создаем агломеративную кластеризацию
ac = AgglomerativeClustering(n_clusters=None, compute_full_tree=True, distance_threshold=0)
labels = ac.fit_predict(X)

2. Изменение порога расстояния

После того как у вас уже есть работающая модель, вы можете пересчитать метки для нового значения distance_threshold. Для этого вам нужно будет рекурсивно пройтись по массиву children_ и использовать информацию из distances_.

3. Реализация функции для переоценки меток

import numpy as np

# Дерево слияний
children = ac.children_
distances = ac.distances_
n_samples = X.shape[0]  # Общее количество точек данных

def get_branch(label): 
    for idx, child in enumerate(children):
        if label in child:
            return idx
    return None

def new_label(label, threshold):
    branch = get_branch(label)
    distance = distances[branch]

    while distance < threshold:
        # Рассмотрим родительский узел
        parent = branch + n_samples  
        branch = get_branch(parent)   
        if branch is None:  # Если родительский узел не существует, выходим
            break
        distance = distances[branch]  

    return label if branch is None else parent

# Пример использования с новым значением порога
threshold = 1.5
new_label_result = new_label(100, threshold)  # Замените 100 на индекс узла, который хотите перетасовать
print(f'Новая метка для узла 100 при пороге {threshold}: {new_label_result}')

4. Пояснение функции

Функция get_branch находит индекс узла, базируясь на переданном значении label.
Функция new_label будет перебирать узлы дерева, пока их расстояние меньше заданного порога threshold. Если расстояние превышает порог, остановите рекурсию и верните новую метку.

Заключение

Следуя вышеописанным шагам, вы сможете эффективно пересчитывать метки агломеративной кластеризации при изменении значения distance_threshold, избегая повторного выполнения полной кластеризации и существенно сокращая время обработки для больших наборов данных.