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

Извлечение признаков с помощью TfidfVectorizer

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

from sklearn.feature_extraction.text import TfidfVectorizer

vectorizer = TfidfVectorizer(
    max_df=0.5,
    min_df=5,
    stop_words="english",
)
t0 = time()
X_tfidf = vectorizer.fit_transform(dataset.data)

print(f"vectorization done in {time() - t0:.3f} s")
print(f"n_samples: {X_tfidf.shape[0]}, n_features: {X_tfidf.shape[1]}")

vectorization done in 0.472 s
n_samples: 3387, n_features: 7929

После исключения терминов, встречающихся более чем в 50% документов (параметр max_df=0.5), и терминов, присутствующих менее чем в 5 документах (параметр min_df=5), количество уникальных терминов n_features составляет около 8 000. Дополнительно можно оценить разреженность матрицы X_tfidf как долю ненулевых элементов от общего числа элементов.

print(f"{X_tfidf.nnz / np.prod(X_tfidf.shape):.3f}")

0.007

Мы видим, что ненулевыми являются около 0,7% элементов матрицы X_tfidf.

Кластеризация разреженных данных методом k-средних

Поскольку и KMeans, и MiniBatchKMeans оптимизируют невыпуклую целевую функцию, их кластеризация не обязательно будет оптимальной при заданной случайной инициализации. Более того, при работе с разреженными данными высокой размерности, например с текстом, векторизованным с помощью модели «мешок слов», k-средних может разместить центроиды в крайне изолированных точках данных. Такие точки могут оставаться собственными центроидами на протяжении всего процесса.

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

from sklearn.cluster import KMeans

for seed in range(5):
    kmeans = KMeans(
        n_clusters=true_k,
        max_iter=100,
        n_init=1,
        random_state=seed,
    ).fit(X_tfidf)
    cluster_ids, cluster_sizes = np.unique(kmeans.labels_, return_counts=True)
    print(f"Number of elements assigned to each cluster: {cluster_sizes}")
print()
print(
    "True number of documents in each category according to the class labels: "
    f"{category_sizes}"
)

Number of elements assigned to each cluster: [ 481  675 1785  446]
Number of elements assigned to each cluster: [1689  638  480  580]
Number of elements assigned to each cluster: [   1    1    1 3384]
Number of elements assigned to each cluster: [1887  311  332  857]
Number of elements assigned to each cluster: [ 291  673 1771  652]

True number of documents in each category according to the class labels: [799 973 987 628]

Чтобы избежать этой проблемы, можно увеличить число запусков с независимыми случайными инициализациями n_init. В этом случае выбирается кластеризация с наилучшей инерцией (целевой функцией k-средних).

kmeans = KMeans(
    n_clusters=true_k,
    max_iter=100,
    n_init=5,
)

fit_and_evaluate(kmeans, X_tfidf, name="KMeans\non tf-idf vectors")

clustering done in 0.20 ± 0.05 s
Homogeneity: 0.349 ± 0.010
Completeness: 0.398 ± 0.009
V-measure: 0.372 ± 0.009
Adjusted Rand-Index: 0.203 ± 0.017
Silhouette Coefficient: 0.007 ± 0.000

Максимальное значение всех этих метрик оценки кластеризации равно 1,0 (при идеальной кластеризации). Чем выше значение, тем лучше. Значения скорректированного индекса Рэнда, близкие к 0,0, соответствуют случайной разметке. По приведённым выше оценкам видно, что распределение по кластерам заметно лучше случайного, но общее качество, безусловно, можно улучшить.

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

Уменьшение размерности с помощью LSA

Алгоритм n_init=1 всё ещё можно использовать, если сначала уменьшить размерность векторизованного пространства, чтобы сделать k-средних более стабильным. Для этого мы используем TruncatedSVD, работающий с матрицами количества терминов/tf-idf. Поскольку результаты SVD не нормализованы, мы повторно выполняем нормализацию, чтобы улучшить результат KMeans. Использование SVD для уменьшения размерности векторов документов TF-IDF в литературе по информационному поиску и интеллектуальному анализу текста часто называют латентно-семантическим анализом (LSA).

from sklearn.decomposition import TruncatedSVD
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import Normalizer

lsa = make_pipeline(TruncatedSVD(n_components=100), Normalizer(copy=False))
t0 = time()
X_lsa = lsa.fit_transform(X_tfidf)
explained_variance = lsa[0].explained_variance_ratio_.sum()

print(f"LSA done in {time() - t0:.3f} s")
print(f"Explained variance of the SVD step: {explained_variance * 100:.1f}%")

LSA done in 0.347 s
Explained variance of the SVD step: 18.4%

Использование одной инициализации сократит время обработки как для KMeans, так и для MiniBatchKMeans.

kmeans = KMeans(
    n_clusters=true_k,
    max_iter=100,
    n_init=1,
)

fit_and_evaluate(kmeans, X_lsa, name="KMeans\nwith LSA on tf-idf vectors")

clustering done in 0.02 ± 0.01 s
Homogeneity: 0.400 ± 0.014
Completeness: 0.431 ± 0.013
V-measure: 0.415 ± 0.011
Adjusted Rand-Index: 0.317 ± 0.016
Silhouette Coefficient: 0.030 ± 0.000

Мы видим, что кластеризация документов в представлении LSA выполняется значительно быстрее (как благодаря n_init=1, так и благодаря намного меньшей размерности пространства признаков LSA). Кроме того, улучшились все метрики оценки кластеризации. Повторим эксперимент с MiniBatchKMeans.

from sklearn.cluster import MiniBatchKMeans

minibatch_kmeans = MiniBatchKMeans(
    n_clusters=true_k,
    n_init=1,
    init_size=1000,
    batch_size=1000,
)

fit_and_evaluate(
    minibatch_kmeans,
    X_lsa,
    name="MiniBatchKMeans\nwith LSA on tf-idf vectors",
)

clustering done in 0.03 ± 0.01 s
Homogeneity: 0.303 ± 0.117
Completeness: 0.342 ± 0.067
V-measure: 0.315 ± 0.103
Adjusted Rand-Index: 0.268 ± 0.125
Silhouette Coefficient: 0.024 ± 0.004

Наиболее значимые термины в каждом кластере

Поскольку TfidfVectorizer можно инвертировать, мы можем определить центры кластеров, которые дают представление о наиболее влиятельных словах для каждого кластера. Сравнение с наиболее предсказательными словами для каждого целевого класса см. в скрипте Классификация текстовых документов с использованием разреженных признаков.

original_space_centroids = lsa[0].inverse_transform(kmeans.cluster_centers_)
order_centroids = original_space_centroids.argsort()[:, ::-1]
terms = vectorizer.get_feature_names_out()

for i in range(true_k):
    print(f"Cluster {i}: ", end="")
    for ind in order_centroids[i, :10]:
        print(f"{terms[ind]} ", end="")
    print()

Cluster 0: thanks graphics image know files file program looking software does
Cluster 1: space launch orbit nasa shuttle earth moon like mission just
Cluster 2: god jesus bible believe christian faith people say does christians
Cluster 3: think don people just say know like time did does

HashingVectorizer

Альтернативную векторизацию можно выполнить с помощью экземпляра HashingVectorizer, который не выполняет взвешивание IDF, поскольку эта модель не хранит состояние (метод fit ничего не делает). Если требуется взвешивание IDF, его можно добавить, передав выходные данные HashingVectorizer в конвейере экземпляру TfidfTransformer. В этом случае мы также добавляем LSA в конвейер, чтобы уменьшить размерность и разреженность хешированного векторного пространства.

from sklearn.feature_extraction.text import HashingVectorizer, TfidfTransformer

lsa_vectorizer = make_pipeline(
    HashingVectorizer(stop_words="english", n_features=50_000),
    TfidfTransformer(),
    TruncatedSVD(n_components=100, random_state=0),
    Normalizer(copy=False),
)

t0 = time()
X_hashed_lsa = lsa_vectorizer.fit_transform(dataset.data)
print(f"vectorization done in {time() - t0:.3f} s")

vectorization done in 1.816 s

Можно заметить, что этап LSA занимает относительно много времени при обучении, особенно для хешированных векторов. Причина в том, что хешированное пространство обычно велико (в этом примере задано значение n_features=50_000). Можно попробовать уменьшить число признаков, пожертвовав этим ради увеличения доли признаков с хеш-коллизиями, как показано в блокноте с примером Сравнение FeatureHasher и DictVectorizer.

Теперь обучим и оценим экземпляры kmeans и minibatch_kmeans на этих данных, уменьшенных с помощью hashing и LSA:

fit_and_evaluate(kmeans, X_hashed_lsa, name="KMeans\nwith LSA on hashed vectors")

clustering done in 0.02 ± 0.00 s
Homogeneity: 0.396 ± 0.006
Completeness: 0.442 ± 0.009
V-measure: 0.418 ± 0.007
Adjusted Rand-Index: 0.341 ± 0.030
Silhouette Coefficient: 0.030 ± 0.001

fit_and_evaluate(
    minibatch_kmeans,
    X_hashed_lsa,
    name="MiniBatchKMeans\nwith LSA on hashed vectors",
)

clustering done in 0.03 ± 0.01 s
Homogeneity: 0.317 ± 0.088
Completeness: 0.336 ± 0.092
V-measure: 0.326 ± 0.089
Adjusted Rand-Index: 0.272 ± 0.104
Silhouette Coefficient: 0.027 ± 0.003

Оба метода дают хорошие результаты, сопоставимые с результатами тех же моделей на традиционных векторах LSA (без хеширования).