組み込みのグラデーション降下オプティマイザを使用するイントロチュートリアルは、多くの意味があります。しかし、k-meansは勾配降下にプラグインできるだけのものではありません。独自のオプティマイザを作成する必要があるようですが、TensorFlowプリミティブを使用すると、それをどうやって行うのかはよく分かりません。TensorFlowでk-meansを実装するにはどうすればよいですか?
どのようなアプローチをとるべきですか?
組み込みのグラデーション降下オプティマイザを使用するイントロチュートリアルは、多くの意味があります。しかし、k-meansは勾配降下にプラグインできるだけのものではありません。独自のオプティマイザを作成する必要があるようですが、TensorFlowプリミティブを使用すると、それをどうやって行うのかはよく分かりません。TensorFlowでk-meansを実装するにはどうすればよいですか?
どのようなアプローチをとるべきですか?
(注:あなたが今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つのクラスタに行くと、問題の例を回避している。私はそれをもう少し明確にし、「例に値する」にするために、以前から私の答えを更新しました。)
のほとんどは私が今まで見てきた答えは、2次元バージョン(2次元でポイントをクラスタリングする必要がある場合)にのみ焦点を当てています。ここでは、任意の次元でのクラスタリングの実装を示します。 Nで
k-means algorithmの基本的な考え方は暗く:
です。
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
のナンを得るでしょう。ちょうど私はおそらくそれが少し良く説明しなければならないtf.contrib.learn.KMeansClustering
を使用しています。それはN点をとり、それらのK個のコピーを作る。それはKの現在の重心を取り、それらのN個のコピーを作る。次に、これらの2つの大きなテンソルを引いて、各点から各重心までのN * Kの距離を得る。それらの距離の平方和を計算し、 'argmin'を使って各点について最良のものを見つける。 次に、dynamic_partitionを使用して、クラスター割り当てに基づいてポイントをK個の異なるテンソルにグループ化し、それらのクラスター内の平均を見つけ出し、それに基づいてセントロイドを設定します。 – dga