Dokumentbiclustering mit dem Spektralen Co-Clustering-Algorithmus

Einführung

In diesem Lab verwenden wir den Spectral Co-Clustering-Algorithmus auf dem Twenty Newsgroups-Datensatz, um die Dokumente zu biclustern. Der Datensatz enthält 20 Kategorien von Dokumenten, und wir werden die Kategorie "comp.os.ms-windows.misc" ausschließen, da sie Beiträge ohne Daten enthält. Die mit TF-IDF vektorisierten Beiträge bilden eine Worthäufigkeitsmatrix, die dann mit Dhillons Spectral Co-Clustering-Algorithmus biclustert wird. Die resultierenden Dokument-Wort-Bicluster zeigen die Teilmengen von Wörtern an, die in diesen Teilmengen von Dokumenten häufiger verwendet werden. Wir werden auch die Dokumente mit MiniBatchKMeans clusteren, um einen Vergleich durchzuführen.

Tipps für die VM

Nachdem der VM-Start abgeschlossen ist, klicken Sie in der oberen linken Ecke, um zur Registerkarte Notebook zu wechseln und Jupyter Notebook für die Übung zu nutzen.

Manchmal müssen Sie einige Sekunden warten, bis Jupyter Notebook vollständig geladen ist. Die Validierung von Vorgängen kann aufgrund von Einschränkungen in Jupyter Notebook nicht automatisiert werden.

Wenn Sie während des Lernens Probleme haben, können Sie Labby gerne fragen. Geben Sie nach der Sitzung Feedback, und wir werden das Problem für Sie prompt beheben.

Bibliotheken importieren

Wir werden die erforderlichen Bibliotheken für dieses Lab importieren.

from collections import defaultdict
import operator
from time import time
import numpy as np
from sklearn.cluster import SpectralCoclustering
from sklearn.cluster import MiniBatchKMeans
from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.cluster import v_measure_score

Definiere Zahlen-Normalisierer

Wir werden eine Funktion number_normalizer() definieren, um alle numerischen Token auf einen Platzhalter zuzuordnen. Dies wird zur Dimensionsreduzierung verwendet.

def number_normalizer(tokens):
    """Map all numeric tokens to a placeholder.

    For many applications, tokens that begin with a number are not directly
    useful, but the fact that such a token exists can be relevant.  By applying
    this form of dimensionality reduction, some methods may perform better.
    """
    return ("#NUMBER" if token[0].isdigit() else token for token in tokens)

Definiere NumberNormalizingVectorizer

Wir werden eine Klasse NumberNormalizingVectorizer() definieren, die von TfidfVectorizer() erbt, um einen Tokenizer zu erstellen, der die zuvor definierte Funktion number_normalizer() verwendet.

class NumberNormalizingVectorizer(TfidfVectorizer):
    def build_tokenizer(self):
        tokenize = super().build_tokenizer()
        return lambda doc: list(number_normalizer(tokenize(doc)))

Lade und bereite Daten vor

Wir werden den Twenty Newsgroups-Datensatz laden und die Kategorie "comp.os.ms-windows.misc" ausschließen. Wir werden auch den Vektorizer definieren.

categories = [
    "alt.atheism",
    "comp.graphics",
    "comp.sys.ibm.pc.hardware",
    "comp.sys.mac.hardware",
    "comp.windows.x",
    "misc.forsale",
    "rec.autos",
    "rec.motorcycles",
    "rec.sport.baseball",
    "rec.sport.hockey",
    "sci.crypt",
    "sci.electronics",
    "sci.med",
    "sci.space",
    "soc.religion.christian",
    "talk.politics.guns",
    "talk.politics.mideast",
    "talk.politics.misc",
    "talk.religion.misc",
]
newsgroups = fetch_20newsgroups(categories=categories)
y_true = newsgroups.target

vectorizer = NumberNormalizingVectorizer(stop_words="english", min_df=5)

Vektorisieren von Daten

Wir werden die Daten mit dem zuvor definierten Vektorizer vektorisieren.

X = vectorizer.fit_transform(newsgroups.data)

Biclustering mit dem Spektralen Co-Clustering-Algorithmus

Wir werden Biclustering mit dem Spektralen Co-Clustering-Algorithmus durch die Definition eines Co-Clusters und das Anpassen an die Daten durchführen.

cocluster = SpectralCoclustering(
    n_clusters=len(categories), svd_method="arpack", random_state=0
)
cocluster.fit(X)
y_cocluster = cocluster.row_labels_

Clustern mit MiniBatchKMeans

Wir werden die Daten mit MiniBatchKMeans clustern.

kmeans = MiniBatchKMeans(
    n_clusters=len(categories), batch_size=20000, random_state=0, n_init=3
)
y_kmeans = kmeans.fit_predict(X)

Finde die besten Bicluster

Wir werden die besten Bicluster finden, indem wir ihre normalisierten Schnitte berechnen und die fünf besten auswählen.

feature_names = vectorizer.get_feature_names_out()
document_names = list(newsgroups.target_names[i] for i in newsgroups.target)

def bicluster_ncut(i):
    rows, cols = cocluster.get_indices(i)
    if not (np.any(rows) and np.any(cols)):
        import sys
        return sys.float_info.max
    row_complement = np.nonzero(np.logical_not(cocluster.rows_[i]))[0]
    col_complement = np.nonzero(np.logical_not(cocluster.columns_[i]))[0]
    weight = X[rows][:, cols].sum()
    cut = X[row_complement][:, cols].sum() + X[rows][:, col_complement].sum()
    return cut / weight

bicluster_ncuts = list(bicluster_ncut(i) for i in range(len(newsgroups.target_names)))
best_idx = np.argsort(bicluster_ncuts)[:5]

Drucke die Ergebnisse

Wir werden die Ergebnisse der besten Bicluster aus Schritt 8 ausgeben.

for idx, cluster in enumerate(best_idx):
    n_rows, n_cols = cocluster.get_shape(cluster)
    cluster_docs, cluster_words = cocluster.get_indices(cluster)
    if not len(cluster_docs) or not len(cluster_words):
        continue

    ## Kategorien
    counter = defaultdict(int)
    for i in cluster_docs:
        counter[document_names[i]] += 1
    cat_string = ", ".join(
        "{:.0f}% {}".format(float(c) / n_rows * 100, name)
        for name, c in most_common(counter)[:3]
    )

    ## Wörter
    out_of_cluster_docs = cocluster.row_labels_!= cluster
    out_of_cluster_docs = np.where(out_of_cluster_docs)[0]
    word_col = X[:, cluster_words]
    word_scores = np.array(
        word_col[cluster_docs, :].sum(axis=0)
        - word_col[out_of_cluster_docs, :].sum(axis=0)
    )
    word_scores = word_scores.ravel()
    important_words = list(
        feature_names[cluster_words[i]] for i in word_scores.argsort()[:-11:-1]
    )

    print("bicluster {} : {} Dokumente, {} Wörter".format(idx, n_rows, n_cols))
    print("Kategorien   : {}".format(cat_string))
    print("Wörter        : {}\n".format(", ".join(important_words)))

Zusammenfassung

In diesem Lab haben wir gelernt, wie man Biclustering mit dem Spektralen Co-Clustering-Algorithmus auf dem Twenty Newsgroups-Dataset durchführt. Wir haben auch gelernt, wie man die Daten mit MiniBatchKMeans clustert, um einen Vergleich durchzuführen. Schließlich haben wir die besten Bicluster gefunden, indem wir ihren normalisierten Schnitt berechnet und die fünf besten ausgewählt haben.