Поправка на случайность при оценке качества кластеризации

Определение списка метрик для оценки

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

• V-мера — среднее гармоническое полноты и однородности;
• индекс Rand, измеряющий, насколько часто пары точек данных группируются согласованно с результатом работы алгоритма кластеризации и назначением истинных меток классов;
• скорректированный индекс Rand (ARI) — индекс Rand с поправкой на случайность, для которого ожидаемое значение при случайном назначении кластеров равно 0,0;
• взаимная информация (MI) — теоретико-информационная мера, количественно оценивающая зависимость между двумя разметками. Обратите внимание, что максимальное значение MI для идеальной разметки зависит от числа кластеров и образцов;
• нормализованная взаимная информация (NMI) — взаимная информация, значения которой лежат между 0 (отсутствие взаимной информации) при большом количестве точек данных и 1 (полное совпадение назначений меток с точностью до перестановки меток). Эта мера не скорректирована на случайность: если число кластеризованных точек данных недостаточно велико, ожидаемые значения MI или NMI для случайной разметки могут быть существенно отличны от нуля;
• скорректированная взаимная информация (AMI) — взаимная информация с поправкой на случайность. Как и в случае с ARI, ожидаемое значение AMI при случайном назначении кластеров равно 0,0.

Дополнительную информацию см. в модуле Оценка качества кластеризации.

from sklearn import metrics

score_funcs = [
    ("V-measure", metrics.v_measure_score),
    ("Rand index", metrics.rand_score),
    ("ARI", metrics.adjusted_rand_score),
    ("MI", metrics.mutual_info_score),
    ("NMI", metrics.normalized_mutual_info_score),
    ("AMI", metrics.adjusted_mutual_info_score),
]

Первый эксперимент: фиксированные истинные метки и растущее число кластеров

Сначала определим функцию, создающую случайную разметку с равномерным распределением.

import numpy as np

rng = np.random.RandomState(0)


def random_labels(n_samples, n_classes):
    return rng.randint(low=0, high=n_classes, size=n_samples)

Другая функция будет использовать функцию random_labels, чтобы создать фиксированный набор истинных меток (labels_a), распределённых в n_classes, а затем оценить несколько наборов случайных «предсказанных» меток (labels_b), чтобы оценить изменчивость заданной метрики при заданном n_clusters.

def fixed_classes_uniform_labelings_scores(
    score_func, n_samples, n_clusters_range, n_classes, n_runs=5
):
    scores = np.zeros((len(n_clusters_range), n_runs))
    labels_a = random_labels(n_samples=n_samples, n_classes=n_classes)

    for i, n_clusters in enumerate(n_clusters_range):
        for j in range(n_runs):
            labels_b = random_labels(n_samples=n_samples, n_classes=n_clusters)
            scores[i, j] = score_func(labels_a, labels_b)
    return scores

В этом первом примере число классов (истинное число кластеров) равно n_classes=10. Число кластеров принимает значения, заданные в n_clusters_range.

import matplotlib.pyplot as plt
import seaborn as sns

n_samples = 1000
n_classes = 10
n_clusters_range = np.linspace(2, 100, 10).astype(int)
plots = []
names = []

sns.color_palette("colorblind")
plt.figure(1)

for marker, (score_name, score_func) in zip("d^vx.,", score_funcs):
    scores = fixed_classes_uniform_labelings_scores(
        score_func, n_samples, n_clusters_range, n_classes=n_classes
    )
    plots.append(
        plt.errorbar(
            n_clusters_range,
            scores.mean(axis=1),
            scores.std(axis=1),
            alpha=0.8,
            linewidth=1,
            marker=marker,
        )[0]
    )
    names.append(score_name)

plt.title(
    "Clustering measures for random uniform labeling\n"
    f"against reference assignment with {n_classes} classes"
)
plt.xlabel(f"Number of clusters (Number of samples is fixed to {n_samples})")
plt.ylabel("Score value")
plt.ylim(bottom=-0.05, top=1.05)
plt.legend(plots, names, bbox_to_anchor=(0.5, 0.5))
plt.show()

Индекс Rand достигает насыщения при n_clusters > n_classes. Другие нескорректированные меры, такие как V-мера, демонстрируют линейную зависимость между числом кластеров и числом образцов.

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

Второй эксперимент: изменение числа классов и кластеров

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

def uniform_labelings_scores(score_func, n_samples, n_clusters_range, n_runs=5):
    scores = np.zeros((len(n_clusters_range), n_runs))

    for i, n_clusters in enumerate(n_clusters_range):
        for j in range(n_runs):
            labels_a = random_labels(n_samples=n_samples, n_classes=n_clusters)
            labels_b = random_labels(n_samples=n_samples, n_classes=n_clusters)
            scores[i, j] = score_func(labels_a, labels_b)
    return scores

В этом случае мы используем n_samples=100, чтобы показать эффект, возникающий, когда число кластеров близко к числу образцов или равно ему.

n_samples = 100
n_clusters_range = np.linspace(2, n_samples, 10).astype(int)

plt.figure(2)

plots = []
names = []

for marker, (score_name, score_func) in zip("d^vx.,", score_funcs):
    scores = uniform_labelings_scores(score_func, n_samples, n_clusters_range)
    plots.append(
        plt.errorbar(
            n_clusters_range,
            np.median(scores, axis=1),
            scores.std(axis=1),
            alpha=0.8,
            linewidth=2,
            marker=marker,
        )[0]
    )
    names.append(score_name)

plt.title(
    "Clustering measures for 2 random uniform labelings\nwith equal number of clusters"
)
plt.xlabel(f"Number of clusters (Number of samples is fixed to {n_samples})")
plt.ylabel("Score value")
plt.legend(plots, names)
plt.ylim(bottom=-0.05, top=1.05)
plt.show()

Мы наблюдаем результаты, схожие с результатами первого эксперимента: метрики с поправкой на случайность остаются вблизи нуля, тогда как значения других метрик обычно растут при увеличении детализации разметки. Среднее значение V-меры для случайной разметки существенно возрастает по мере того, как число кластеров приближается к общему числу образцов, используемых для вычисления метрики. Кроме того, взаимная информация без нормализации не ограничена сверху, а её масштаб зависит от размерности задачи кластеризации и числа истинных классов. Поэтому кривая выходит за пределы графика.

Таким образом, только скорректированные меры можно безопасно использовать в качестве согласованного индекса для оценки средней стабильности алгоритмов кластеризации при заданном значении k на различных перекрывающихся подвыборках набора данных.

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

Общее время выполнения скрипта: (0 минут 1,139 секунды)

Download Jupyter notebook: plot_adjusted_for_chance_measures.ipynb

Download Python source code: plot_adjusted_for_chance_measures.py

Download zipped: plot_adjusted_for_chance_measures.zip

Связанные примеры

Демонстрация алгоритма кластеризации DBSCAN

Кластеризация текстовых документов с помощью k-средних

Выбор числа кластеров с помощью силуэтного анализа при кластеризации методом KMeans

Агломеративная кластеризация с различными метриками