Comment implémenterais-je k-means avec TensorFlow?

Question

Le didacticiel d'intro, qui utilise l'optimiseur de descente de gradient intégré, a beaucoup de sens. Cependant, k-means n'est pas seulement quelque chose que je peux intégrer dans la descente en dégradé. Il semble que je devrais écrire mon propre type d'optimiseur, mais je ne suis pas sûr de savoir comment le faire étant donné les primitives TensorFlow.

Quelle approche dois-je prendre?

Answer 1

(Remarque: Vous pouvez maintenant obtenir a more polished version of this code as a gist on github.)

vous pouvez certainement le faire, mais vous devez définir vos propres critères d'optimisation (pour k-means, il est généralement un nombre maximum d'itération et lorsque le l'affectation se stabilise). Voici un exemple de la façon dont vous pourriez le faire (il y a probablement des façons plus optimales de l'implémenter, et certainement de meilleurs moyens de sélectionner les points initiaux). Il est fondamentalement comme vous le feriez dans numpy si vous essayiez vraiment difficile de rester loin de faire les choses de manière itérative en python:

import tensorflow as tf 
import numpy as np 
import time 

N=10000 
K=4 
MAX_ITERS = 1000 

start = time.time() 

points = tf.Variable(tf.random_uniform([N,2])) 
cluster_assignments = tf.Variable(tf.zeros([N], dtype=tf.int64)) 

# Silly initialization: Use the first two points as the starting     
# centroids. In the real world, do this better.         
centroids = tf.Variable(tf.slice(points.initialized_value(), [0,0], [K,2])) 

# Replicate to N copies of each centroid and K copies of each      
# point, then subtract and compute the sum of squared distances.     
rep_centroids = tf.reshape(tf.tile(centroids, [N, 1]), [N, K, 2]) 
rep_points = tf.reshape(tf.tile(points, [1, K]), [N, K, 2]) 
sum_squares = tf.reduce_sum(tf.square(rep_points - rep_centroids), 
          reduction_indices=2) 

# Use argmin to select the lowest-distance point         
best_centroids = tf.argmin(sum_squares, 1) 
did_assignments_change = tf.reduce_any(tf.not_equal(best_centroids, 
                cluster_assignments)) 

def bucket_mean(data, bucket_ids, num_buckets): 
    total = tf.unsorted_segment_sum(data, bucket_ids, num_buckets) 
    count = tf.unsorted_segment_sum(tf.ones_like(data), bucket_ids, num_buckets) 
    return total/count 

means = bucket_mean(points, best_centroids, K) 

# Do not write to the assigned clusters variable until after      
# computing whether the assignments have changed - hence with_dependencies 
with tf.control_dependencies([did_assignments_change]): 
    do_updates = tf.group(
     centroids.assign(means), 
     cluster_assignments.assign(best_centroids)) 

sess = tf.Session() 
sess.run(tf.initialize_all_variables()) 

changed = True 
iters = 0 

while changed and iters < MAX_ITERS: 
    iters += 1 
    [changed, _] = sess.run([did_assignments_change, do_updates]) 

[centers, assignments] = sess.run([centroids, cluster_assignments]) 
end = time.time() 
print ("Found in %.2f seconds" % (end-start)), iters, "iterations" 
print "Centroids:" 
print centers 
print "Cluster assignments:", assignments 

(Notez qu'une réelle mise en œuvre devrait être plus prudent sur la sélection initiale du cluster, éviter les cas de problèmes avec tous les points allant à un cluster, etc Ceci est juste une démo rapide.J'ai mis à jour ma réponse de plus tôt pour le rendre un peu plus clair et "digne d'exemple".)

Answer 2

La plupart des Les réponses que j'ai vues jusqu'ici se concentrent uniquement sur la version 2d (lorsque vous devez regrouper des points en 2 dimensions). Voici ma mise en œuvre de la mise en cluster dans des dimensions arbitraires.

---

idée de base de k-means algorithm n obscurcit:

• générer des points de départ k aléatoire
• Pour ce faire, jusqu'à ce que vous dépassiez la patience ou l'affectation de cluster ne change pas:
  • assign chaque point au point de départ le plus proche
  • recalculer l'emplacement de chaque point de départ en prenant t il moyenne entre son groupe

---

Pour pouvoir valider en quelque sorte les résultats que je vais tenter de regrouper les images MNIST.

import numpy as np 
import tensorflow as tf 
from random import randint 
from collections import Counter 
from tensorflow.examples.tutorials.mnist import input_data 

mnist = input_data.read_data_sets("MNIST_data/") 
X, y, k = mnist.test.images, mnist.test.labels, 10 

Voici X mes données au cluster (10000, 784), y est le nombre réel et k est le nombre de grappes (qui est le même que le nombre de chiffres. Maintenant, la réelle algorithme:.

# select random points as a starting position. You can do better by randomly selecting k points. 
start_pos = tf.Variable(X[np.random.randint(X.shape[0], size=k),:], dtype=tf.float32) 
centroids = tf.Variable(start_pos.initialized_value(), 'S', dtype=tf.float32) 

# populate points 
points   = tf.Variable(X, 'X', dtype=tf.float32) 
ones_like  = tf.ones((points.get_shape()[0], 1)) 
prev_assignments = tf.Variable(tf.zeros((points.get_shape()[0],), dtype=tf.int64)) 

# find the distance between all points: http://stackoverflow.com/a/43839605/1090562 
p1 = tf.matmul(
    tf.expand_dims(tf.reduce_sum(tf.square(points), 1), 1), 
    tf.ones(shape=(1, k)) 
) 
p2 = tf.transpose(tf.matmul(
    tf.reshape(tf.reduce_sum(tf.square(centroids), 1), shape=[-1, 1]), 
    ones_like, 
    transpose_b=True 
)) 
distance = tf.sqrt(tf.add(p1, p2) - 2 * tf.matmul(points, centroids, transpose_b=True)) 

# assign each point to a closest centroid 
point_to_centroid_assignment = tf.argmin(distance, axis=1) 

# recalculate the centers 
total = tf.unsorted_segment_sum(points, point_to_centroid_assignment, k) 
count = tf.unsorted_segment_sum(ones_like, point_to_centroid_assignment, k) 
means = total/count 

# continue if there is any difference between the current and previous assignment 
is_continue = tf.reduce_any(tf.not_equal(point_to_centroid_assignment, prev_assignments)) 

with tf.control_dependencies([is_continue]): 
    loop = tf.group(centroids.assign(means), prev_assignments.assign(point_to_centroid_assignment)) 

sess = tf.Session() 
sess.run(tf.global_variables_initializer()) 

# do many iterations. Hopefully you will stop because of has_changed is False 
has_changed, cnt = True, 0 
while has_changed and cnt < 300: 
    cnt += 1 
    has_changed, _ = sess.run([is_continue, loop]) 

# see how the data is assigned 
res = sess.run(point_to_centroid_assignment) 

maintenant, il est de vérifier de temps à quel point sont nos grappes Pour ce faire, nous regrouperons tous les nombres réels qui sont apparus dans le cluster ensemble après que nous verrons des choix les plus populaires dans ce cluster.. Dans un cas de t Le regroupement parfait nous aura la seule valeur dans chaque groupe. Dans le cas d'un cluster aléatoire, chaque valeur sera approximativement représentée de manière égale dans le groupe.

nums_in_clusters = [[] for i in xrange(10)] 
for cluster, real_num in zip(list(res), list(y)): 
    nums_in_clusters[cluster].append(real_num) 

for i in xrange(10): 
    print Counter(nums_in_clusters[i]).most_common(3) 

Cela me donne quelque chose comme ceci:

[(0, 738), (6, 18), (2, 11)] 
[(1, 641), (3, 53), (2, 51)] 
[(1, 488), (2, 115), (7, 56)] 
[(4, 550), (9, 533), (7, 280)] 
[(7, 634), (9, 400), (4, 302)] 
[(6, 649), (4, 27), (0, 14)] 
[(5, 269), (6, 244), (0, 161)] 
[(8, 646), (5, 164), (3, 125)] 
[(2, 698), (3, 34), (7, 14)] 
[(3, 712), (5, 290), (8, 110)] 

C'est assez bonne parce que la majorité des chefs d'accusation est dans le premier groupe. Vous voyez que le regroupement confond 7 et 9, 4 et 5. Mais 0 est regroupé plutôt bien.

Quelques approches comment améliorer cela:

• exécuter l'algorithme plusieurs fois et sélectionnez le meilleur (en fonction de la distance aux clusters)
• des cas de manipulation quand rien est affecté à un grappe. Dans mon cas, vous obtiendrez Nan dans la variable means car count est 0.
• initialisation de points aléatoires.

Answer 3

il suffit d'utiliser tf.contrib.learn.KMeansClustering