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

Извлечение признаков с использованием 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.479 s
n_samples: 3387, n_features: 7929

После игнорирования терминов, которые встречаются более чем в 50% документов (как установлено max_df=0.5) и терминов, которые отсутствуют по крайней мере в 5 документах (установлено min_df=5), полученное количество уникальных терминов n_features составляет около 8000. Мы также можем количественно оценить разреженность 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.23 ± 0.06 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

K-средних всё ещё можно использовать, если сначала понизить размерность векторизованного пространства, чтобы сделать 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.408 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.00 s
Homogeneity: 0.400 ± 0.012
Completeness: 0.430 ± 0.012
V-measure: 0.414 ± 0.009
Adjusted Rand-Index: 0.315 ± 0.014
Silhouette Coefficient: 0.030 ± 0.001

Мы можем наблюдать, что кластеризация по представлению 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.02 ± 0.00 s
Homogeneity: 0.286 ± 0.089
Completeness: 0.326 ± 0.055
V-measure: 0.302 ± 0.074
Adjusted Rand-Index: 0.222 ± 0.106
Silhouette Coefficient: 0.025 ± 0.003

Топ-термины по кластеру

Поскольку 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: just think don know like ve time does did said
Cluster 1: space launch orbit nasa shuttle earth moon like mission solar
Cluster 2: graphics thanks image program file know files looking help format
Cluster 3: god people jesus believe don bible say think religion christian

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.991 s

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

Теперь мы подгоняем и оцениваем экземпляры kmeans и minibatch_kmeans на этих данных, уменьшенных с помощью hashed-lsa:

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

clustering done in 0.02 ± 0.01 s
Homogeneity: 0.387 ± 0.011
Completeness: 0.429 ± 0.017
V-measure: 0.407 ± 0.013
Adjusted Rand-Index: 0.328 ± 0.023
Silhouette Coefficient: 0.029 ± 0.001

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

clustering done in 0.02 ± 0.00 s
Homogeneity: 0.357 ± 0.043
Completeness: 0.378 ± 0.046
V-measure: 0.367 ± 0.043
Adjusted Rand-Index: 0.322 ± 0.030
Silhouette Coefficient: 0.028 ± 0.004

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