Définissez votre propre fonction de distance avec k-means de scikit-learn
Que présenter dans cet article
- La fonction de distance des kmeans est-elle vraiment une justice de distance euclidienne?
- Qu'est-ce qui fonctionne avec les k-means de scikit-learn?
- Comment changer la fonction de distance avec k-means de scikit-learn?
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.
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.
- É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
- Utilisez la méthode k-centroid. Il semble qu'il puisse être utilisé avec scikit-learn. Je ne l'ai pas vérifié.
- 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é.
- Lorsque Y est Aucun
- Lorsque X est un tableau d'un échantillon et Y est un tableau de plusieurs échantillons
- 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é
- La fonction de distance de k-means n'est pas la grande justice de la distance euclidienne
- L'utilisation d'autres fonctions de distance avec scikit-learn est un peu pénible
- Lent
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