TensorFlowでk-meansを実装するにはどうすればよいですか？

Question

組み込みのグラデーション降下オプティマイザを使用するイントロチュートリアルは、多くの意味があります。しかし、k-meansは勾配降下にプラグインできるだけのものではありません。独自のオプティマイザを作成する必要があるようですが、TensorFlowプリミティブを使用すると、それをどうやって行うのかはよく分かりません。

どのようなアプローチをとるべきですか？

Answer 1

（注：あなたが今a more polished version of this code as a gist on githubを得ることができます。）

（K-手段のために、それは通常、最大反復回数だとするとき、あなたは間違いなくそれを行うことができますが、あなたがあなた自身の最適化基準を定義する必要があります割り当てが安定する）。ここでは、どのように行うかの例を示します（実装にはおそらく最適な方法があり、最初の点を選択する方法は間違いありません）。それはあなたが繰り返しのpythonで物事をやってから離れて滞在するために本当にハードにしようとしていた場合は、numpyの中でそれを行うだろうように、基本的です：

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 

は（実際の実装は、最初のクラスタの選択について詳しくは注意する必要があることに注意してください、これはただ速いデモであ​​るなど、すべての点が1つのクラスタに行くと、問題の例を回避している。私はそれをもう少し明確にし、「例に値する」にするために、以前から私の答えを更新しました。）

Answer 2

のほとんどは私が今まで見てきた答えは、2次元バージョン（2次元でポイントをクラスタリングする必要がある場合）にのみ焦点を当てています。ここでは、任意の次元でのクラスタリングの実装を示します。 Nで

---

k-means algorithmの基本的な考え方は暗く：

• アサインを：
  • あなたは忍耐を超えたり、クラスタの割り当ては変更されませんまで、ランダムなk個の出発点
  • これを行う生成しますそれぞれが最も近い開始点を指す
  • tをとることによって各開始点の位置を再計算する彼はそれの間で平均何とか私は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 

は、だからここXYは実数であり、Kは、桁数と同じであるクラスタの番号（ある、(10000, 784)をクラスタ化するために私のデータである。今、実際のアルゴリズム：

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

今では時間である私達のクラスターであるどのように良いチェック我々はグループが一緒にクラスタに登場したすべての実数意志これを行うにはその後、我々はそのクラスタの中で最も人気のある選択肢が表示されます。。。 tの場合彼は完璧なクラスタリングを、各グループにただ一つの価値しか持たないでしょう。ランダムクラスタの場合、各値はグループ内でほぼ等しく表される。カウントの大半は最初のグループであるため、

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

これはかなり良いです：

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) 

この

は私にこのような何かを提供します。あなたはクラスタリングが7と9と4と5を混乱させることを知っています。でも、0はきれいにクラスタ化されています。これを改善する方法を

いくつかのアプローチ：

• は、アルゴリズムを数回実行し、何が割り当てられていないとき
• 取扱例（クラスターへの距離に基づいて）最適なものを選択しますクラスタ。私の場合、countが0なので、meansのナンを得るでしょう。
• ランダムポイントの初期化。

Answer 3

ちょうど私はおそらくそれが少し良く説明しなければならないtf.contrib.learn.KMeansClustering