Spectral clustering の実装に関するメモ

##ポイント
* Spectral clustering を実装し、具体的な数値例で確認。

##データ
```python
from sklearn.datasets import make_moons

n_input = 100

x, labels = make_moons(n_samples = n_input, noise = 0.05)

plt.scatter(x[:,0], x[:, 1], c = labels, cmap = 'Accent')

plt.show()
```
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/3fef5391-74a6-ad7d-c5cc-100cb4f5150a.png)

##サンプルコード　(K-means clustering)
```python
tf.reset_default_graph()

# K-means clustering
def k_means(x, n_clusters):
  r_seed = np.random.randint(100)
  graph = tf.contrib.factorization.KMeans(x, num_clusters = n_clusters, \
                                         random_seed = r_seed)

  return graph.training_graph()


n_clusters = 2
x_input = x.astype(np.float32)

all_scores, cluster_idx, scores, cluster_centers_initialized, init_op, training_op = k_means(x_input, n_clusters)
    
init_var = tf.global_variables_initializer()

with tf.Session() as sess:
  sess.run(init_var)
  sess.run(init_op)
  cluster_idx_init = sess.run(cluster_idx)
  
  for i in range(10):
    sess.run(training_op)
    
  cluster_idx_last = sess.run(cluster_idx)
  
#print (labels)  
#print (cluster_idx_init[0])
#print (cluster_idx_last[0])

#plt.scatter(x[:,0], x[:, 1], c = cluster_idx_init[0], cmap = 'RdBu')
#plt.show()

plt.scatter(x[:,0], x[:, 1], c = cluster_idx_last[0], cmap = 'RdBu')
plt.title('K-means clustering')
plt.show()
```

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/9cff1cdb-7c29-59e8-fdcb-e448356927e1.png)

##サンプルコード　(Spectral clustering)
```python
tf.reset_default_graph()

# Spectral Clustering
def squared_distance(x, n_input):
  X = tf.expand_dims(x, 1)
  M = tf.tile(X, [1, n_input, 1])
  M_T = tf.transpose(M, [1, 0, 2])

  return tf.reduce_sum(tf.square(M - M_T), axis = -1)

def full_affinity(x, n_input, scale = 1.0):
  S = squared_distance(x, n_input)

  return tf.exp(-0.5 * S / scale**2)

def knn_affinity(x, n_input, n_nbrs):
  S = squared_distance(x, n_input)

  nn = tf.nn.top_k(-S, n_nbrs, sorted = True)
  nn_var = nn[0]
  nn_idx = nn[1]

  jj = tf.reshape(nn_idx, [-1, 1])
  ii = tf.range(n_input)
  ii = tf.reshape(ii, [-1, 1])
  ii = tf.tile(ii, [1, n_nbrs])
  ii = tf.reshape(ii, [-1, 1])
  indices = tf.concat([ii, jj], axis = 1)

  mask = tf.SparseTensor(indices = tf.cast(indices, tf.int64), values = [1.0]*n_input*n_nbrs, dense_shape = [n_input, n_input])
  mask = tf.sparse_reorder(mask)
  mask = tf.sparse_tensor_to_dense(mask)

  scale_squared = tf.reduce_mean(-nn_var[:, n_nbrs - 1])

  W = tf.exp(-0.5 * S / scale_squared) * mask
    
  W = 0.5 * (W + tf.transpose(W))
  
  return W

def laplacian(W):

  # unnormalized Laplacian
  diag = tf.reduce_sum(W, axis = -1)
  D = tf.matrix_diag(diagonal = diag)
  L = D - W 
  e, v = tf.self_adjoint_eig(L)

  # normalized Laplacian
  D_I = tf.matrix_diag(diagonal = 1.0 / diag)
  L_rw = tf.matmul(D_I, L)
  e_rw, v_rw = tf.self_adjoint_eig(L_rw)

  return v, v_rw

def k_means(x, n_clusters):
  r_seed = np.random.randint(100)
  graph = tf.contrib.factorization.KMeans(x, num_clusters = n_clusters, \
                                         random_seed = r_seed)

  return graph.training_graph()

n_clusters = 2
n_nbrs = 5
x_input = x.astype(np.float32)

#W = full_affinity(x_input, n_input, 1)
W = knn_affinity(x_input, n_input, n_nbrs)
v, v_rw = laplacian(W)
y = v[:, :n_clusters]
all_scores, cluster_idx, scores, cluster_centers_initialized, init_op, training_op = k_means(y, n_clusters)
    
init_var = tf.global_variables_initializer()

with tf.Session() as sess:
  sess.run(init_var)
  sess.run(init_op)
  cluster_idx_init = sess.run(cluster_idx)
  
  for i in range(10):
    sess.run(training_op)
    
  cluster_idx_last = sess.run(cluster_idx)
  
#print (labels)  
#print (cluster_idx_init[0])
#print (cluster_idx_last[0])

#plt.scatter(x[:,0], x[:, 1], c = cluster_idx_init[0], cmap = 'RdBu')
#plt.title('Spectral Clustering')
#plt.show()

plt.scatter(x[:,0], x[:, 1], c = cluster_idx_last[0], cmap = 'RdBu')
plt.title('Spectral Clustering')
plt.show()
```
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/8fc3f2f1-9d50-b7e7-6b4d-471862adf000.png)