k means - contrib - ¿Cómo implementaría k-means con TensorFlow?

tensorflow contrib factorization k means

Question

El tutorial introductorio, que utiliza el optimizador de descenso degradado incorporado, tiene mucho sentido. Sin embargo, k-means no es solo algo que puedo conectar al descenso de gradiente. Parece que tendría que escribir mi propio tipo de optimizador, pero no estoy muy seguro de cómo hacerlo dado los primitivos de TensorFlow.

¿Qué enfoque debo tomar?

Answer 1

La mayoría de las respuestas que he visto hasta ahora se centran solo en la versión 2d (cuando necesitas agrupar puntos en 2 dimensiones). Aquí está mi implementación de la agrupación en dimensiones arbitrarias.

Idea básica del algoritmo k-means en n dims:

• generar al azar k puntos de partida
• haga esto hasta que exceda la paciencia o la asignación del clúster no cambie:
  • asignar cada punto al punto de partida más cercano
  • recalcular la ubicación de cada punto de partida tomando el promedio entre su grupo

Para poder validar de alguna manera los resultados, intentaré agrupar las imágenes 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

Entonces, aquí X es mi información para agrupar (10000, 784) , y es el número real, yk es el número de clúster (que es lo mismo que el número de dígitos. Ahora el algoritmo real:

# 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://.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)

Ahora es el momento de comprobar qué tan buenos son nuestros clusters. Para hacer esto agruparemos juntos todos los números reales que aparecieron en el grupo. Después de eso, veremos las opciones más populares en ese clúster. En el caso del agrupamiento perfecto tendremos el único valor en cada grupo. En caso de clúster aleatorio, cada valor se representará de manera aproximadamente igual en el grupo.

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)

Esto me da algo como esto:

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

Esto es bastante bueno porque la mayoría de los conteos está en el primer grupo. Usted ve que la agrupación confunde 7 y 9, 4 y 5. Pero 0 se agrupa muy bien.

Algunos enfoques cómo mejorar esto:

• ejecutar el algoritmo varias veces y seleccionar el mejor (según la distancia a los clusters)
• manejo de casos cuando no se asigna nada a un clúster. En mi caso obtendrás Nan en variable means porque count es 0.
• inicialización de puntos aleatorios.

Answer 2

solo use tf.contrib.learn.KMeansClustering

Answer 3

(nota: ahora puede obtener una versión más pulida de este código como esencia en github ).

definitivamente puede hacerlo, pero necesita definir sus propios criterios de optimización (para k-means, usualmente es un recuento máximo de iteraciones y cuando la asignación se estabiliza). Aquí hay un ejemplo de cómo podría hacerlo (probablemente haya formas más óptimas de implementarlo, y definitivamente mejores formas de seleccionar los puntos iniciales). Básicamente es como si lo hubieras hecho en numpy si estuvieras tratando realmente de mantenerte alejado de hacer cosas iterativamente 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

(Tenga en cuenta que una implementación real debería ser más cuidadosa con la selección inicial del clúster, evitando casos problemáticos con todos los puntos dirigidos a un clúster, etc. Esta es solo una demostración rápida. He actualizado mi respuesta anterior para que sea un poco más claro y "digno de ejemplo").