Dynamic Time Warping & k-medoids

##Data
```python
temp = pd.read_csv('.../temperature.csv')
data = temp.iloc[:, 1:]
 
print ('shape: ', temp.shape)
temp

plt.figure(figsize = (7, 5))
plt.plot(np.arange(1, 13), data)
plt.legend(data.columns, loc='upper left')
plt.title('Monthly average temperature')
plt.show()
```
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/cffbe9f7-20bd-9d30-2758-213a04fab8d6.png)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/9ae1f2f4-4ce4-ad3f-7d34-33058ebd5a63.png)

##Dynamic Time Warping (DTW)
```python
def dtw(vec1, vec2):
  d = np.zeros([len(vec1)+1, len(vec2)+1])
  d[:] = np.inf
  d[0, 0] = 0
  for i in range(1, d.shape[0]):
    for j in range(1, d.shape[1]):
      cost = abs(vec1[i-1]-vec2[j-1])
      d[i, j] = cost + min(d[i-1, j], d[i, j-1], d[i-1, j-1])
  return d[-1][-1]

dtw_mat = []

for col1, col2 in product(data.columns, data.columns):
  dtw_mat.append(dtw(data[col1].values, data[col2].values))
  
dtw_mat = np.reshape(np.array(dtw_mat), (9, 9))

plt.figure(figsize = (7, 5))
sns.heatmap(dtw_mat, annot=True, linewidths=0.1, linecolor='white')
plt.title('DTW Distance Matrix')
plt.show()
```

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/2e63fad7-d4b0-4cd1-4cc8-2a2ff8be509e.png)


##k-medoids
```python
class KMedoids():
  def __init__(self, n_cluster, max_iter=300):

    self.n_cluster = n_cluster
    self.max_iter = max_iter

  def fit_predict(self, D):

    m, n = D.shape

    initial_medoids = np.random.choice(range(m), self.n_cluster, replace=False)
    tmp_D = D[:, initial_medoids]

    labels = np.argmin(tmp_D, axis=1)

    results = pd.DataFrame([range(m), labels]).T
    results.columns = ['id', 'label']

    col_names = ['x_' + str(i + 1) for i in range(m)]
    results = pd.concat([results, pd.DataFrame(D, columns=col_names)], axis=1)

    before_medoids = initial_medoids
    new_medoids = []

    loop = 0
    while ((len(set(before_medoids).intersection(set(new_medoids))) != self.n_cluster) 
           and (loop < self.max_iter) ):

      if loop > 0:
        before_medoids = new_medoids.copy()
        new_medoids = []

      for i in range(self.n_cluster):
        tmp = results[results['label'] == i].copy()

        tmp['distance'] = np.sum(tmp.loc[:, ['x_' + str(id + 1) 
                                            for id in tmp['id']]].values, axis=1)
        tmp = tmp.reset_index(drop=True)
        new_medoids.append(tmp.loc[tmp['distance'].idxmin(), 'id'])

      new_medoids = sorted(new_medoids)
      tmp_D = D[:, new_medoids]

      clustaling_labels = np.argmin(tmp_D, axis=1)
      results['label'] = clustaling_labels

      loop += 1

    results = results.loc[:, ['id', 'label']]
    results['flag_medoid'] = 0
    
    for medoid in new_medoids:
      results.loc[results['id'] == medoid, 'flag_medoid'] = 1
      
    tmp_D = pd.DataFrame(tmp_D, columns=['medoid_distance'+str(i) 
                                         for i in range(self.n_cluster)])
    results = pd.concat([results, tmp_D], axis=1)

    self.results = results
    self.cluster_centers_ = new_medoids

    return results['label'].values

km = KMedoids(3, 300)
pred = km.fit_predict(dtw_mat)

print ('cluster predict: ', pred)
```
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/04b1ab2d-722a-d5dc-e5b5-a17c3ec109e9.png)

```python
col_0 = data.columns[pred==0]
col_1 = data.columns[pred==1]
col_2 = data.columns[pred==2]

print ('cluster 0')
print (data.loc[:, [col for col in col_0]].describe())
print ()
print ('cluster 1')
print (data.loc[:, [col for col in col_1]].describe())
print ()
print ('cluster 2')
print (data.loc[:, [col for col in col_2]].describe())
```

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/d4c95868-a457-cfeb-b8af-b5cd29050661.png)


##k-means
```python
data_2 = data.values.T
print ('shape: ', data_2.shape)
print ()

km = KMeans(n_clusters=3)
pred = km.fit_predict(data_2)
print ('cluster predict: ', pred)
```
 
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254604/1791dff4-d36d-13cb-d9d6-42ef7b068f64.png)