Jak zaimplementować k-średnich z TensorFlow?

Question

Samouczek wstępu, który korzysta z wbudowanego optymalizatora pochylenia gradientu, ma wiele sensu. Jednak K-oznacza nie jest czymś, co mogę podłączyć do gradientu. Wygląda na to, że musiałbym napisać własny optymalizator, ale nie jestem do końca pewien, jak to zrobić, biorąc pod uwagę prymitywy TensorFlow.

Jakie podejście powinienem zastosować?

Answer 1

(uwaga: można teraz dostać a more polished version of this code as a gist on github.)

pewno można to zrobić, ale trzeba definiować własne kryteria optymalizacji (K-drodze, to zazwyczaj max liczba iteracji i kiedy przydział stabilizuje się). Oto przykład tego, jak możesz to zrobić (prawdopodobnie istnieją bardziej optymalne sposoby jego implementacji i zdecydowanie lepsze sposoby wyboru punktów początkowych). Jest to w zasadzie jak można to zrobić w numpy jeśli starali naprawdę trudno się trzymać z dala od robienia rzeczy iteracyjnie w Pythonie:

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 

(Należy pamiętać, że prawdziwa realizacja musiałaby być bardziej ostrożnym wstępnej selekcji klastra, unikanie problemów z wszystkimi punktami przechodzącymi do jednego klastra itp. To tylko szybkie demo. Zaktualizowałem moją wcześniejszą odpowiedź, aby była nieco bardziej przejrzysta i "godna polecenia".)

Answer 2

Większość Odpowiedzi, które do tej pory widziałem, koncentrują się tylko na wersji 2d (kiedy trzeba zgrupować punkty w 2 wymiarach). Oto moja implementacja klastrowania w dowolnych wymiarach.

---

Podstawowa idea k-means algorithm w N przyciemnia:

• wygenerować losowy k punkty startowe
• to zrobić, dopóki nie przekroczy cierpliwości lub przypisanie klaster nie zmienia:
  • Przypisz każdy punkt do najbliższego punktu początkowego
  • ponownie obliczyć położenie każdego punktu początkowego, biorąc on średnio między nim znajduje się klaster

---

Aby móc jakoś potwierdzić wyniki postaram się klastra MNIST obrazów.

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 

Więc X moje dane do klastra (10000, 784), y jest liczba rzeczywista, a k jest numer klastra (która jest taka sama jak liczba cyfr. Teraz rzeczywisty algorytm:..

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

teraz to sprawdzić czas jak dobre są nasze klastry do tego będziemy grupa wszystkie liczby rzeczywiste, które pojawiły się w zestawie razem Po tym będziemy zobaczyć najbardziej popularnych wyborów w tym klastrze zrobić. W przypadku t on doskonałe skupienie będziemy mieli tylko jedną wartość w każdej grupie. W przypadku przypadkowego klastra każda wartość będzie w przybliżeniu jednakowo reprezentowana w grupie.

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) 

To daje mi coś takiego:

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

to dość dobre, ponieważ większość zarzutów jest w pierwszej grupie. Widzisz, że klastrowanie myli 7 i 9, 4 i 5. Ale 0 jest zgrupowane całkiem ładnie.

Kilka podejść jak ulepszyć ten:

• uruchomić algorytm kilka razy i wybrać najlepszą z nich (w zależności od odległości do gromad)
• prowadzenie spraw, gdy nic nie jest przypisany do grupa. W moim przypadku otrzymasz Nan w zmiennej means, ponieważ count jest 0.
• inicjalizacja punktów losowych.

Answer 3

wystarczy użyć tf.contrib.learn.KMeansClustering