Définissez votre propre fonction de distance avec k-means de scikit-learn

Que présenter dans cet article

En parlant de la méthode k-means, comme vous le savez tous, c'est celle qui divise les données.

C'est quelque chose qui apparaît souvent dans les manuels, donc je ne vais pas l'expliquer en détail, mais ce qui est encore utilisé est (matière interdite).

Oh, au fait, ce genre de vidéo ou ce genre d'outil, Je pense que c'est bien de bien comprendre le mouvement de k-means.

Ainsi, dans k-means, une "fonction de distance" est nécessaire pour mesurer la distance entre le centroïde et chaque donnée.

Dans les manuels, la "distance euclidienne" est souvent choisie, mais est-ce vraiment correct?

Cet article, Anna Huang, «Similarity Measures for Text Document Clustering», 2008

Répondra clairement à une telle question.

Jetons un coup d'œil au tableau 4 emprunté au document. Puisqu'il s'agit d'un index d'entropie, un regroupement plus faible est meilleur.

スクリーンショット 2015-11-04 20.24.24.png

Vous pouvez voir que la distance euclidienne n'est pas justice dans la tâche de classification de texte.

Ensuite, c'est l'humanité qui donne envie d'essayer d'autres fonctions à distance.

Essayons avec scikit-learn

En conclusion, une telle option n'existe pas.

Mendokusei pour enquêter. Ce n'est pas vraiment.

Vous pouvez voir cela en regardant le code scikit-learn.

    closest_dist_sq = euclidean_distances(
        centers[0, np.newaxis], X, Y_norm_squared=x_squared_norms,
        squared=True)
    current_pot = closest_dist_sq.sum()

C'est extrait de code k-means, mais la distance euclidienne est codée en dur Tu peux voir ça.

En d'autres termes, il n'y a pas de place pour changer la fonction de distance en option.

Mais qu'est-ce que c'est pas? En regardant problèmes github, il dit quelque chose comme "parce qu'il est difficile de généraliser avec d'autres fonctions de distance". Il y a.

Pourtant, j'aimerais en faire une option cachée ...

Alors, comment utilisez-vous d'autres fonctions de distance! ??

Il semble y avoir plusieurs façons.

  1. Écrivez vous-même k-signifie. C'est sur la page de débordement de pile (http://stackoverflow.com/questions/5529625/is-it-possible-to-specify-your-own-distance-function-using-scikit-learn-k-means) La méthode s'écrit
  2. Utilisez la méthode k-centroid. Il semble qu'il puisse être utilisé avec scikit-learn. Je ne l'ai pas vérifié.
  3. Utilisez monkey-patch. Cette fois, je vais le faire.

Qu'est-ce que monkey-patch? En d'autres termes, "écrasez la méthode et faites ce que vous voulez".

Cette fois, écrasons la fonction de distance euclidienne dans k-means. Cette page décrit comment procéder.

Faisons-le réellement.

Les données à utiliser sont empruntées à ici. Ce ne sont pas des données textuelles, mais c'est mignon ...

Voyons le comportement de la distance euclidienne de scikit-learn

La distance euclidienne que k-means appelle est this.

Le comportement peut être grossièrement divisé.

  1. Lorsque Y est Aucun
  2. Lorsque X est un tableau d'un échantillon et Y est un tableau de plusieurs échantillons
  3. Lorsque X est un tableau de 2 échantillons et Y est un tableau de plusieurs échantillons

est.

Dans tous les cas

array([
    [Distance entre X et Y]
])

Renvoie un tableau du formulaire.

Ainsi, lorsque vous définissez une nouvelle fonction de distance, vous suivrez ce format.

Mettre en œuvre la fonction de distance du coefficient de corrélation de Pearson

Implémentons le coefficient de corrélation de Pearson introduit dans l'article. En python, il est Disponible dans scipy.

Cependant, comme mentionné dans l'article, cela ne devient pas une fonction de distance en l'état. Par conséquent, je vais changer un peu la formule.

special_pearsonr(X, Y) = {
    1 - pearsonr(X, Y) if pearsonr(X, Y) > 0,
    |pearsonr(X, Y)| else
}

La formule est transformée.

Maintenant, implémentons-le en tenant compte des trois cas de distance euclidienne.

def special_pearsonr(X, Y):
    pearsonr_value = scipy.stats.pearsonr(X, Y)
    if pearsonr_value[0] < 0:
        return abs(pearsonr_value[0])
    else:
        return 1 - pearsonr_value[0]


def sub_pearsonr(X, row_index_1, row_index_2):
    pearsonr_distance = special_pearsonr(X[row_index_1], X[row_index_2])
    return (row_index_1, row_index_2, pearsonr_distance)


def pearsonr_distances(X, Y=None):
    if Y==None:
        #Seul X est entré et X est 2d-Pour tableau
        row_combinations = list(combinations(range(0, len(X)), 2))
        pearsonr_set = [sub_pearsonr(X, index_set_tuple[0], index_set_tuple[1]) for index_set_tuple in row_combinations]
        matrix_source_data = pearsonr_set + map(copy_inverse_index, pearsonr_set)

        row = [t[0] for t in matrix_source_data]
        col = [t[1] for t in matrix_source_data]
        data = [t[2] for t in matrix_source_data]

        pearsonr_matrix = special_pearsonr((data, (row, col)), (X.shape[0], X.shape[0]))
        return pearsonr_matrix.toarray()

    elif len(X.shape)==1 and len(Y.shape)==2:
        #Lorsque X est un échantillon et Y est plusieurs échantillons
        #return est un tableau de 1 échantillon
        pearsonr_set = numpy.array([special_pearsonr(X, Y[y_sample_index]) for y_sample_index in range(0, Y.shape[0])])

        return pearsonr_set

    elif len(X.shape)==2 and len(Y.shape)==2:
        #X sur une ligne[i]Andy[j] in n(Y)Enregistrer et renvoyer la distance
        # X[i]Une fonction qui calcule toutes les distances entre et Y
        pearsonr_x_and_all_y = lambda X, Y: numpy.array([special_pearsonr(X, Y[y_sample_index]) for y_sample_index in range(0, Y.shape[0])])
        pearsonr_divergence_set = numpy.array([pearsonr_x_and_all_y(X[x_i], Y) for x_i in range(0, X.shape[0])])
        return pearsonr_divergence_set
    else:
        raise Exception("Exception case caused")

La fonction de distance que pearsonr_distances appelle avec k-means.

Maintenant, nous allons monkey-patch la fonction de distance euclidienne.

start = time.time()

#Pour garantir l'entrée, préparez une fonction avec les mêmes paramètres que la fonction de distance euclidienne.
def new_euclidean_distances(X, Y=None, Y_norm_squared=None, squared=False):
    return pearsonr_distances(X, Y)

from sklearn.cluster import k_means_

#Écraser ici!
k_means_.euclidean_distances = new_euclidean_distances
kmeans_model = KMeans(n_clusters=3, random_state=10, init='random').fit(features)
print(kmeans_model.labels_)
elapsed_time = time.time() - start
print ("Pearsonr k-means:{0}".format(elapsed_time))

Je voulais voir le temps d'exécution, alors j'ai décidé de mesurer le temps aussi.

J'ai oublié de dire que les données sont

features = numpy.array([
        [  80,  85, 100 ],
        [  96, 100, 100 ],
        [  54,  83,  98 ],
        [  80,  98,  98 ],
        [  90,  92,  91 ],
        [  84,  78,  82 ],
        [  79, 100,  96 ],
        [  88,  92,  92 ],
        [  98,  73,  72 ],
        [  75,  84,  85 ],
        [  92, 100,  96 ],
        [  96,  92,  90 ],
        [  99,  76,  91 ],
        [  75,  82,  88 ],
        [  90,  94,  94 ],
        [  54,  84,  87 ],
        [  92,  89,  62 ],
        [  88,  94,  97 ],
        [  42,  99,  80 ],
        [  70,  98,  70 ],
        [  94,  78,  83 ],
        [  52,  73,  87 ],
        [  94,  88,  72 ],
        [  70,  73,  80 ],
        [  95,  84,  90 ],
        [  95,  88,  84 ],
        [  75,  97,  89 ],
        [  49,  81,  86 ],
        [  83,  72,  80 ],
        [  75,  73,  88 ],
        [  79,  82,  76 ],
        [ 100,  77,  89 ],
        [  88,  63,  79 ],
        [ 100,  50,  86 ],
        [  55,  96,  84 ],
        [  92,  74,  77 ],
        [  97,  50,  73 ],
])

est. Quand je l'exécute,

[0 0 0 1 1 2 1 0 2 1 0 2 2 0 0 1 1 0 1 0 2 0 2 0 2 2 1 1 2 1 1 2 2 2 1 2 2]
Pearsonr k-means:11.0138161182

J'ai pu confirmer que cela fonctionnait fermement! Yattane!

À propos, le k-moyen normal, la version de distance euclidienne est

[1 1 0 1 1 2 1 1 2 1 1 1 2 1 1 0 2 1 0 0 2 0 2 0 1 1 1 0 2 2 2 2 2 2 0 2 2]
========================================
Normal k-means:0.016499042511

est. Vous pouvez voir s'il existe des données avec différents clusters de 0 et 1.

Le temps d'exécution est ... Malheureusement, il y a une différence de près de 600 fois ...

Il n'y a aucune aide pour cela car le nombre de fonctions à appeler a augmenté. Il y a de fortes chances que ce soit un peu plus rapide si la mise en œuvre est conçue. (Des gens érotiques qui vont accélérer. Recrutement)

Je n'ai pas vu la différence parce que je ne l'ai pas utilisé pour la classification des documents, mais comme cela a été prouvé dans l'article, le coefficient de corrélation de Pearson donnera sûrement de bons résultats (devrait être ...)

Résumé


Au fait ...

J'ai également implémenté Calback Livener Distance. Cependant, malheureusement, cela s'arrête avec une erreur.

Lors de la mesure de la distance entre X et Y, un facteur négatif est inévitablement généré et la distance devient inf, de sorte qu'elle ne peut même pas être initialisée en premier lieu.

Je me demande quoi faire des facteurs négatifs, mais que dois-je faire? Je ne l'ai pas mentionné dans mon article.

from sklearn.preprocessing import normalize
def averaged_kullback_leibler(X, Y):
    #norm_X = normalize(X=X, norm='l1')[0]
    #norm_Y = normalize(X=Y, norm='l1')[0]
    norm_X = X
    norm_Y = Y

    pie_1 = norm_X / (norm_X + norm_Y)
    pie_2 = norm_Y / (norm_X + norm_Y)
    M = (pie_1 * norm_X) + (pie_2 * norm_Y)

    KLD_averaged = (pie_1 * scipy.stats.entropy(pk=norm_X, qk=M)) + (pie_2 * scipy.stats.entropy(pk=norm_Y, qk=M))

    return KLD_averaged

def sub_KL_divergence(X, row_index_1, row_index_2):
    #kl_distance = scipy.stats.entropy(pk=X[row_index_1], qk=X[row_index_2])
    kl_distance = averaged_kullback_leibler(X[row_index_1], X[row_index_2])
    return (row_index_1, row_index_2, kl_distance)

def copy_inverse_index(row_col_data_tuple):
    return (row_col_data_tuple[1], row_col_data_tuple[0], row_col_data_tuple[2])

def KLD_distances(X, Y=None):
    if Y==None:
        #Seul X est entré et X est 2d-Pour tableau
        row_combinations = list(combinations(range(0, len(X)), 2))
        kl_divergence_set = [sub_KL_divergence(X, index_set_tuple[0], index_set_tuple[1]) for index_set_tuple in row_combinations]
        matrix_source_data = kl_divergence_set + map(copy_inverse_index, kl_divergence_set)

        row = [t[0] for t in matrix_source_data]
        col = [t[1] for t in matrix_source_data]
        data = [t[2] for t in matrix_source_data]

        kl_distance_matrix = scipy.sparse.csr_matrix((data, (row, col)), (X.shape[0], X.shape[0]))
        return kl_distance_matrix.toarray()
    elif len(X.shape)==1 and len(Y.shape)==2:
        #Lorsque X est un échantillon et Y est plusieurs échantillons
        #return est un tableau de 1 échantillon
        kl_divergence_set = numpy.array([averaged_kullback_leibler(X, Y[y_sample_index]) for y_sample_index in range(0, Y.shape[0])])

        return kl_divergence_set
    elif len(X.shape)==2 and len(Y.shape)==2:
        #X sur une ligne[i]Andy[j] in n(Y)Enregistrer et renvoyer la distance
        # X[i]Une fonction qui calcule toutes les distances entre et Y
        for x_i in range(0, X.shape[0]):
            xx = X[x_i]
            for y_sample_index in range(0, Y.shape[0]):
                #print(xx)
                #print(Y[y_sample_index])
                print(averaged_kullback_leibler(xx, Y[y_sample_index]))

        kld_x_and_all_y = lambda X, Y: numpy.array([averaged_kullback_leibler(X, Y[y_sample_index]) for y_sample_index in range(0, Y.shape[0])])
        kl_divergence_set = numpy.array([kld_x_and_all_y(X[x_i], Y) for x_i in range(0, X.shape[0])])
        return kl_divergence_set
    else:
        raise Exception("Exception case caused")

Recommended Posts

Définissez votre propre fonction de distance avec k-means de scikit-learn
kmeans ++ avec scikit-learn
Flux de création de votre propre package avec setup.py avec python
Écrivez votre propre fonction d'activation avec Pytorch (sigmoïde dur)
(Suite) Essayez d'autres fonctions de distance avec kmeans dans Scikit-learn
Traitement parallèle avec Parallel de scikit-learn
Exécutez l'intelligence de votre propre bibliothèque python avec VScode.
Résolvez votre propre labyrinthe avec Q Learning
[Introduction au style GAN] Apprentissage unique de l'animation avec votre propre machine ♬
Entraînez UGATIT avec votre propre jeu de données
Résolvez votre propre labyrinthe avec DQN
Calculer AUC avec groupBy of PySpark DataFrame (définir la fonction d'agrégation avec pandas_udf)
Votre propre client Twitter réalisé avec Django
[Renforcer l'apprentissage] DQN avec votre propre bibliothèque
Créez votre propre serveur DNS avec Twisted
Créez votre propre valeur composite avec SQLAlchemy
Pour importer votre propre module avec jupyter
Publiez votre propre bibliothèque Python sur Homebrew
Recevez beaucoup de vos tweets avec Tweepy
J'ai essayé la reconnaissance manuscrite des caractères des runes avec scikit-learn
Essayez de créer votre propre AWS-SDK avec bash
Comparaison d'exemples d'implémentation de k-means de scikit-learn et pyclustering
Comment définir votre propre cible dans Sage
Créez rapidement votre propre module avec setuptools (python)
Prédisez le deuxième tour de l'été 2016 avec scikit-learn
Entraînez Stanford NER Tagger avec vos propres données
Créez une roue de votre propre module OpenCV
Créez votre propre lecteur de musique avec Bottle0.13 + jPlayer2.5!
Étapes pour installer votre propre bibliothèque avec pip