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

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.

Méthode valeur initiale
soft K-means Nombre de distributions normales et moyenne de chaque distribution
Méthode de clustering convexe Distribution de distribution normale(Unifié avec toutes les distributions)

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

facteur niveau
Les données \mathbb{R}^{1}(Données 1D)、\mathbb{R}^{2}(Données 2D)
Nombre de distributions normales utilisées pour l'échantillonnage Quatre
Nombre d'échantillons d'une distribution normale 100 points
L'ampleur de la dispersion de la valeur initiale(grossissement) d'habitude(×1), Grand(×2), Très grand(×10)

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} figure_1.png figure_2.png figure_3.png
\mathbb{R}^{2} figure_4.png figure_5.png figure_6.png

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.

d'habitude Grand Très grand
\mathbb{R}^{1} 46 40 5
\mathbb{R}^{2} 23 11 15

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.

Recommended Posts

Mise en œuvre et expérience de la méthode de clustering convexe
Clustering de méthodes de clustering
Explication et mise en œuvre de SocialFoceModel
[Deep Learning from scratch] Implémentation de la méthode Momentum et de la méthode AdaGrad
Vérification et mise en œuvre de la méthode de reconstruction vidéo en utilisant GRU et Autoencoder
Explication et mise en œuvre de PRML Chapitre 4
Introduction et mise en œuvre de JoCoR-Loss (CVPR2020)
Explication et implémentation de l'algorithme ESIM
Introduction et mise en œuvre de la fonction d'activation
Implémentation Einsum de la méthode d'itération de valeur
Explication et mise en œuvre du perceptron simple
Explication mathématique de la recherche de dichotomie et de trisection et méthode de mise en œuvre sans bogues
[Python] Implémentation de la méthode Nelder – Mead et sauvegarde des images GIF par matplotlib
[Recommandation] Résumé des avantages et des inconvénients de la méthode de filtrage / mise en œuvre basée sur le contenu et coopérative
Explication et implémentation de l'algorithme Decomposable Attention
Comparaison d'exemples d'implémentation de k-means de scikit-learn et pyclustering
Implémentation de l'arbre TRIE avec Python et LOUDS
Implémentation de la méthode de gradient 1
Explication de la distance d'édition et de l'implémentation en Python
Implémentation de la méthode de clustering k-shape pour les données de séries chronologiques [Apprentissage non supervisé avec python Chapitre 13]
[Python] Implémentation du clustering à l'aide d'un modèle gaussien mixte
Fusion de la mise en œuvre du tri / analyse du montant du calcul et de l'expérimentation en Python
Implémentation de la condition de jugement d'authenticité d'objet à l'aide de la méthode __bool__
Mise à jour séquentielle de la co-distribution pour la dérivation et l'implémentation des expressions
Clustering et analyse en composantes principales par méthode K-means (débutant)
Méthode de voisinage #k d'apprentissage automatique et sa mise en œuvre et divers
J'ai touché Bergeronnette (3). Enquête et mise en place de messages pop-up.
Implémentation de l'écran de l'administrateur DB par Flask-Admin et Flask-Login
Comment visualiser les données par variable explicative et variable objective
Expérience de clustering par échantillonnage
Parallélisation de la méthode de classe
Remplacement de méthode et super
Implémentation de la séquence de Fibonacci
Principes de base et mise en œuvre de Perceptron
J'ai considéré la méthode d'apprentissage automatique et son langage d'implémentation à partir des informations de balise de Qiita
Résumé de la méthode d'essai
Implémentation Python du mode de fusion CSS3 et discussion sur l'espace colorimétrique
Augmentez la vitesse de la méthode Monte Carlo de l'implémentation de découpage Cython.
Dérivation et implémentation d'équations de mise à jour pour la décomposition de facteurs tensoriels non négatifs
Une implémentation Python simple de la méthode k-voisinage (k-NN)
Examen de la méthode de prévision des échanges utilisant le Deep Learning et la conversion en ondelettes - Partie 2
Théorie et mise en œuvre de modèles de régression multiple - pourquoi une régularisation est nécessaire -
Simulation acoustique Méthode FDTD Dérivation et mise en œuvre des limites d'absorption de Mur
Implémentation de la méthode ML-EM, algorithme de reconstruction en coupe pour scanner
Explication du CSV et exemple d'implémentation dans chaque langage de programmation