Mise en œuvre et expérience de la méthode de clustering convexe

Code que j'ai écrit

C'est un résultat enfantin, mais j'ai fait Publier le code sur Github.

Les références

• [1] Suite / Reconnaissance de formes facile à comprendre - Introduction à l'apprentissage sans enseignant - (Livre très facile à comprendre!)
• [2] D. Lashkari et P. Golland: Convex clustering with exemplar-based models (Travail original de la méthode de clustering convexe)

Ma compréhension approximative

La méthode de clustering convexe est une méthode de clustering dans laquelle le nombre de classes est inconnu sur la base de l'estimation des paramètres de la distribution normale mixte.

La différence par rapport à l'estimation des paramètres de la distribution normale mixte (ci-après dénommée soft K-means) par l'algorithme EM habituel réside dans les paramètres auxquels des valeurs initiales doivent être attribuées.

Par conséquent, il présente l'avantage d'être moins dépendant de la valeur initiale de la solution que les K-moyens souples.

La probabilité de la distribution normale formée par chaque centroïde est calculée en considérant toutes les données observées comme des centroïdes. Le calcul de la probabilité est unique et seule la probabilité antérieure est mise à jour. Avec la mise à jour, la probabilité a priori des centres de gravité difficiles à former une distribution approche de zéro. Même s'il existe une certaine pré-probabilité, le nombre de centroïdes restants sera le nombre final de classes.

Motivation pour la mise en œuvre

J'étais intéressé car il a été introduit dans la littérature [1]. Il est intéressant qu'il semble facile à mettre en œuvre et qu'il semble moins dépendant de la valeur initiale. En tant qu'approche pour fabriquer des jouets pour mon passe-temps, je m'attendais à ce que ce soit plus facile à utiliser que les baies non paramétriques.

la mise en oeuvre

Implémenté en Python + Numpy. Seule la partie implémentation de la mise à jour des paramètres de la méthode de clustering convexe est affichée.

convex_clustering.py

def calculateLikelihoodCombination(x, sigma, gaussianFunc):
    likelihood = np.empty(0)
    for i1 in x:
        likelihood = np.append(likelihood, gaussianFunc(x, i1, sigma))
    samples = len(x)
    return np.reshape(likelihood, (samples, samples))


def calculatePrior(prePrior, likelihood):
    samples = len(prePrior)
    molecule = (prePrior*likelihood.T).T
    denomin = np.sum(molecule, axis=0) + 1e-10
    return np.sum(molecule/denomin, axis=1)/samples


def runConvexClustering(x, hyperSigma, gaussian, plotter):
    # Pre-calculation of likelihood
    likelihood = calculateLikelihoodCombination(x, hyperSigma, gaussian)
    # Initialize prior probability.
    classNum = len(x)  # Number of samples is used as number of classes.
    firstPrior = 1.0/classNum  # Set non zero value.
    prior = np.repeat(firstPrior, classNum)

    # Update parameters.
    for dummy in range(1000):
        prior = calculatePrior(prior, likelihood)

C'est tellement simple que vous n'avez besoin que de dizaines de lignes. Je pense que c'est plus court que le code soft K-means que j'ai écrit localement dans le passé.

Conditions expérimentales

Le nombre total d'échantillons dans une expérience est de 4 * 100 = 400 points. Le grossissement attaché à l'amplitude de la dispersion de la valeur initiale est le grossissement par rapport à l'écart type de la distribution normale utilisée pour l'échantillonnage.

résultat

Le tableau ci-dessous montre l'état du clustering. L'axe vertical du tableau correspond aux données et l'axe horizontal correspond à l'ampleur de la dispersion de la valeur initiale.

	d'habitude	Grand	Très grand
\mathbb{R}^{1}
\mathbb{R}^{2}

Le bleu est l'échantillon et le vert est la forme de la liaison convexe de la distribution normale générée à partir du centroïde de la classe obtenue par la méthode de regroupement convexe.

De plus, le nombre de classes restantes après la coupe est le suivant. De même, l'axe vertical du tableau correspond aux données et l'axe horizontal correspond à l'ampleur de la dispersion des valeurs initiales.

Considération

Lorsque la distribution de la valeur initiale est [normale, grande], il semble qu'elle soit raisonnablement bien groupée. Je pense que le clustering est plus correct lorsqu'il est [Large]. Lors de l'application à un problème réel, il peut être préférable d'utiliser une distribution légèrement plus grande que prévu. Lorsque la variance de la valeur initiale est [très grande], quatre distributions sont regroupées en une seule distribution. Mais c'est un résultat assez explicite.

Le nombre de centroïdes dans les données secondaires est plus proche du nombre de distributions normales (= 4) utilisées pour générer l'échantillon que dans les données primaires. Ceci est également mentionné dans la référence [2]. Plus l'espace à rechercher est large, plus la dépendance à la valeur initiale de la méthode de clustering convexe sera faible. Cependant, je suis un peu inquiet que le nombre de centroïdes ne se soit pas assez rapproché de 4 comme dans la littérature [1] [2]. \ # J'espère sincèrement que ce n'est pas un bogue dans l'implémentation.

Résumé

Ce que j'ai ressenti à propos de la méthode de clustering convexe à travers l'implémentation et l'expérimentation, c'est que «l'implémentation est très simple, mais il semble y avoir quelques astuces pour l'appliquer à des problèmes réels». Dans la littérature [1] [2], les avantages et les inconvénients sont énoncés dans la discussion, et il semble difficile à utiliser en fonction du problème à traiter. Je pense que c'est une méthode de regroupement rentable, mais je voudrais examiner plus attentivement si c'est une approche appropriée du problème que je veux résoudre.