Come implementare k-means con TensorFlow?

Question

Il tutorial di introduzione, che utilizza l'ottimizzatore di discesa del gradiente incorporato, ha molto senso. Tuttavia, k-means non è solo qualcosa che posso inserire nella discesa del gradiente. Sembra che dovrei scrivere il mio tipo di ottimizzatore, ma non sono abbastanza sicuro di come farlo dato i primitivi di TensorFlow.

Quale approccio devo prendere?

Answer 1

(NOTA: È ora possibile ottenere a more polished version of this code as a gist on github.)

sicuramente si può fare, ma è necessario definire i tuoi criteri di ottimizzazione (per k-means, di solito è un conteggio di iterazione massimo e quando il l'incarico si stabilizza). Ecco un esempio di come potresti farlo (ci sono probabilmente modi più ottimali per implementarlo, e sicuramente modi migliori per selezionare i punti iniziali). E 'fondamentalmente come si farebbe in NumPy se si stavano cercando davvero difficile stare lontano dal fare le cose in modo iterativo in 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 

(Si noti che una reale attuazione avrebbe bisogno di essere più attenti a selezione iniziale cluster, evitando casi problematici con tutti i punti che vanno a un cluster, ecc. Questa è solo una demo rapida. Ho aggiornato la mia risposta da prima per renderla un po 'più chiara e "degna di esempio".)

Answer 2

le risposte che ho visto finora si focalizzano solo sulla versione 2d (quando è necessario raggruppare i punti in 2 dimensioni). Ecco la mia implementazione del clustering in dimensioni arbitrarie.

---

idea di base del k-means algorithm n affievolisce:

• generare casuale k punti di partenza
• fare questo finché si supera la pazienza o la cessione di cluster non cambia:
  • assegnare ogni punto al punto di partenza più vicino
  • ricalcolare la posizione di ciascun punto di partenza tenendo egli media tra grappolo è

---

Per essere in grado di convalidare i risultati in qualche modo cercherò di raggruppare le immagini 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 

Così qui X è i miei dati a raggrupparsi (10000, 784), y è il numero reale, e k è il numero di cluster (che è lo stesso del numero di cifre. Ora l'attuale algoritmo:.

# 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) 

Ora è il momento, controllare quanto bene sono i nostri cluster Per fare questo avremo gruppo tutti i numeri reali che apparivano nel cluster insieme dopo che vedremo le scelte più popolari in quel cluster.. In un caso di t lui perfetto clustering avremo il solo valore in ogni gruppo. In caso di cluster casuale ogni valore sarà approssimativamente ugualmente rappresentato nel gruppo.

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) 

Questo mi dà qualcosa di simile:

[(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)] 

Questo è abbastanza buono perché maggior parte dei conti è nel primo gruppo. Vedete che il clustering confonde 7 e 9, 4 e 5. Ma 0 è in cluster piuttosto bene.

alcuni approcci come migliorare questo:

• eseguire l'algoritmo un paio di volte e selezionare il migliore (sulla base della distanza a cluster)
• casi di manipolazione quando nulla viene assegnato ad un grappolo. Nel mio caso riceverai Nan nella variabile means perché count è 0.
• inizializzazione di punti casuali.

Answer 3

basta usare tf.contrib.learn.KMeansClustering