クラスタリングの精度と実行時間

# 概要
scikit-learnの[公式サイト](https://scikit-learn.org/stable/modules/clustering.html#clustering)には実行時間とクラスタリングをした結果だけで精度がわからないためいくつか選んで実行してまとめた。
そして、実行時間と精度を比較した。 


# 実行環境
Mac Mini(2018)
OS : macOS Mojave 10.14.6
CPU : 3.2GHz 6コア第8世代Intel Core i7
メモリ : 16GB
ストレージ : 256GB
Python : Python 3.7.3

# 用いた手法とベンチマーク
## 手法
以下の4つを用いた。それぞれの説明は他を参照してほしいです。  
### K-Means

``` python
def kmeans(X, y, n):
    """
    K Meansによるクラスタリング

    Parameters
    ----------
    X : numpy array
        データ
    y : numpy array
        正解ラベル
    n : int
        クラスタ数
    Returns
    -------
    acc_km : float
        正解率
    time_km : float
        実行時間
    """
    km = KMeans(n_clusters=n,
                init="random",
                n_init=10,
                max_iter=300,
                random_state=0)
    start_km = time.time()
    y_km = km.fit_predict(X)
    end_km = time.time()
    y_km = np.reshape(y_km, (1, len(y[0])))
    acc_km, _, _ = ACC(y_km, y)
    time_km = round(end_km - start_km, 2)

    make_graph(X, y_km, n)

    return acc_km, time_km
```

### Spectral clustering

```python
def spectralclustering(X, y, n):
    """
    Spectral Clusteringによるクラスタリング

    Parameters
    ----------
    X : numpy array
        データ
    y : numpy array
        正解ラベル
    n : int
        クラスタ数
    Returns
    -------
    acc_sc : float
        正解率
    time_sc : float
        実行時間
    """
    sc = SpectralClustering(n_clusters=2,
                            affinity="nearest_neighbors")
    start_sc = time.time()
    y_sc = sc.fit_predict(X)
    end_sc = time.time()
    y_sc = np.reshape(y_sc, (1, len(y[0])))
    acc_sc, _, _ = ACC(y_sc, y)
    time_sc = round(end_sc - start_sc, 2)

    make_graph(X, y_sc, n)
    
    return acc_sc, time_sc
```
### Agglomerative clustering

```python
def agglomerativeclustering(X, y, n):
    """
    Agglomerative Clusteringを用いたクラスタリング

    Parameters
    ----------
    X : numpy array
        データ
    y : numpy array
        正解ラベル
    n : int
        クラスタ数
    Returns
    acc_ac : float
        正解率
    time_ac : float
        実行時間
    -------
    """
    ac = AgglomerativeClustering(n_clusters=n)
    start_ac = time.time()
    y_ac = ac.fit_predict(X)
    end_ac = time.time()
    y_ac = np.reshape(y_ac, (1, len(y[0])))
    acc_ac, _, _ = ACC(y_ac, y)
    time_ac = round(end_ac - start_ac, 2)
    
    make_graph(X, y_ac, n)

    return acc_ac, time_ac
```
### DBSCAN

```python
def dbscan(X, y, n):
    """
    DBSCANを用いたクラスタリング

    Parameters
    ----------
    X : numpy array
        データ
    y : numpy array
        正解ラベル
    n : int
        クラスタ数
    Returns
    -------
    acc_dbs : float
        正解率
    time_dbs : float
        実行時間
    """
    dbs = DBSCAN(eps=0.1,
                min_samples=2)
    start_dbs = time.time()
    y_dbs = dbs.fit_predict(X)
    end_dbs = time.time()
    y_dbs = np.reshape(y_dbs, (1, len(y[0])))
    acc_dbs, _, _ = ACC(y_dbs, y)
    time_dbs = round(end_dbs - start_dbs, 2)

    make_graph(X, y_dbs, n)

    return acc_dbs, time_dbs
```
### Birch

```python
def birch(X, y, n):
    """
    Birchによるクラスタリング

    Parameters
    ----------
    X : numpy array
        データ
    y : numpy array
        正解ラベル
    n : int
        クラスタ数

    Returns
    -------
    acc_br : float
        正解率
    time_br : float
        実行時間
    """
    br = Birch(n_clusters=2)
    start_br = time.time()
    y_br = br.fit_predict(X)
    end_br = time.time()
    y_br = np.reshape(y_br, (1, len(y[0])))
    acc_br, _, _ = acc(y_br, y)
    time_br = round(end_br - start_br, 2)

    make_graph(X, y_br, n, "Birch")

    return acc_br, time_br
```
### Mini batch K-Means

```python
def minibatchkmeans(X, y, n):
    """
    Mini Batch K Meansによるクラスタリング

    Parameters
    ----------
    X : numpy array
        データ
    y : numpy array
        正解ラベル
    n : int
        クラスタ数

    Returns
    -------
    acc_mbkm : float
        正解率
    time_mbkm : float
        実行時間
    """
    mbkm = MiniBatchKMeans(n_clusters=n,
                init="random",
                n_init=10,
                max_iter=300)
    start_mbkm = time.time()
    y_mbkm = mbkm.fit_predict(X)
    end_mbkm = time.time()
    y_mbkm = np.reshape(y_mbkm, (1, len(y[0])))
    acc_mbkm, _, _ = acc(y_mbkm, y)
    time_mbkm = round(end_mbkm - start_mbkm, 2)

    make_graph(X, y_mbkm, n, "MiniBatchKMeans")

    return acc_mbkm, time_mbkm
```

## ベンチマーク
以下の3+3種類を用いた。
### Two Circle(2つの円の距離が近い場合と遠い場合)
|近い場合|遠い場合|
|---|---|
|![Original.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/9d98b4fa-122a-3718-49a2-71ff53d04008.png)|![Original.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/fb73ecfc-89f2-c045-5c32-8d56844d0357.png)|
### Two Moon(ノイズなしとノイズあり)
|ノイズなし|ノイズあり|
|---|---|
|![Original.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/40e4347f-0108-215a-89b7-4628a87a6d07.png)|![Original.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/2f5cd27f-6df5-84bf-4e58-92e1503d9326.png)|
### Blobs(2つの集合の距離が近い場合と遠い場合)
|近い場合|遠い場合|
|---|---|
|![Original.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/893f4558-b3fb-d264-9b2b-9468d682ba8a.png)|![Original.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/4590273e-db8e-ae56-8a02-555500fcc425.png)|

# 結果
数値は上段が精度で、下段が実行時間[sec].
## Two Circle(2つの円の距離が近い場合)
|K-Means|Spectral Clustering|Agglomerative Clustering|
|---|---|---|
|0.5|1.0|0.5014|
|0.03 sec|11.35 sec|0.42 sec|
|![Kmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/22540cfd-9759-f736-7516-0bcdef4e366a.png)|![SpectralClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/aa40b0f3-22d4-2722-d7a4-b9fc11d80ece.png)|![AgglomerativeClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/7e65d643-d692-bb25-ba24-bdf8f7260e2d.png)|

|DBSCAN|Birch|Mini Batch K-Means|
|---|---|---|
|1.0|0.5002|0.5008|
|0.03 sec|0.08 sec|0.03 sec|
|![DBSCAN.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/b1d04eb1-f402-84ef-cff5-d849d25d0c02.png)|![Birch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/49444182-028c-6edb-5709-bccbd5de82ac.png)|![MiniBatchKmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/8954b67f-f07e-f24f-da27-ad25352ebff3.png)|
## Two Circle(2つの円の距離が遠い場合)
|K-Means|Spectral Clustering|Agglomerative Clustering|
|---|---|---|
|0.7054|1.0|0.6738|
|0.02 sec|9.62 sec|0.4 sec|
|![Kmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/bfc892fd-0b3f-69ef-d8be-c50dca375a5f.png)|![SpectralClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/19f72bc0-5de5-7da3-e39f-436cba0ae177.png)|![AgglomerativeClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/358138da-6e94-0818-c499-d9ef23e7a8fc.png)|

|DBSCAN|Birch|Mini Batch K-Means|
|---|---|---|
|1.0|0.7484|0.7042|
|0.16 sec|0.09 sec|0.03 sec|
|![DBSCAN.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/4fb0b976-dbfe-b4ff-4ab5-e81ef0797970.png)|![Birch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/ade75c4a-91e6-9103-ee99-8260806f4847.png)|![MiniBatchKmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/195e1536-5c49-035c-90b7-2171e249a5c4.png)|
## Two Moon(ノイズなし)
|K-Means|Spectral Clustering|Agglomerative Clustering|
|---|---|---|
|0.752|1.0|0.7918|
|0.03 sec|34.15 sec|0.39 sec|
|![Kmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/df0d7003-618e-6ed0-6c1f-7221a82abcc9.png)|![SpectralClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/1fb46880-fcee-2196-0398-8d79b7672e45.png)|![AgglomerativeClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/8202c7d4-58b2-c409-ad01-af1ed97be877.png)|

|DBSCAN|Birch|Mini Batch K-Means|
|---|---|---|
|1.0|0.7184|0.7548|
|0.03 sec|0.08 sec|0.04 sec|
|![DBSCAN.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/b557778b-6a27-34b2-295d-6b5c91406db2.png)|![Birch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/e29195df-cb53-df26-c1e4-3abea44ea6c2.png)|![MiniBatchKmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/a82a0638-7d9e-3e28-7c7b-2519b55dbfcd.png)|
## Two Moon(ノイズあり)
|K-Means|Spectral Clustering|Agglomerative Clustering|
|---|---|---|
|0.7532|1.0|0.8226|
|0.03 sec|4.96 sec|0.43 sec|
|![Kmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/02168758-16fd-6d72-3be2-9eab69bc5040.png)|![SpectralClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/fd20bc9b-fa50-9124-6b91-048af0c8984d.png)|![AgglomerativeClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/60bc76ee-7825-0f6f-8908-ee8cad4aa683.png)|

|DBSCAN|Birch|Mini Batch K-Means|
|---|---|---|
|1.0|0.9072|0.7554|
|0.03 sec|0.08 sec|0.05 sec|
|![DBSCAN.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/cbdeb08a-137d-52f9-8ab2-0b463440a3cd.png)|![Birch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/ac6d21aa-1c53-ad6d-9ed3-9d9f13284f07.png)|![MiniBatchKmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/fd44427f-2618-1dd2-09c7-7e932782e651.png)|
## Blobs(2つの集合の距離が近い場合)
|K-Means|Spectral Clustering|Agglomerative Clustering|
|---|---|---|
|0.9786|0.9778|0.9712|
|0.02 sec|0.43 sec|0.42 sec|
|![Kmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/69d795ba-e01e-18ed-ebd8-04e309e49dbe.png)|![SpectralClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/54f44ee1-edbd-84ca-f01f-c848517e5cb6.png)|![AgglomerativeClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/706de828-dcaa-4093-1146-ce03c5086c70.png)|

|DBSCAN|Birch|Mini Batch K-Means|
|---|---|---|
|0.5004|0.8692|0.9772|
|0.01 sec|0.15 sec|0.02 sec|
|![DBSCAN.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/ee24cf13-d7aa-c637-b2cc-6b883d7fd058.png)|![Birch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/14a3502a-f3da-25fb-2159-b96d4a5527d0.png)|![MiniBatchKmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/b2bcab4c-ab91-342c-9b88-ea2c099be66b.png)|
## Blobs(2つの集合の距離が遠い場合)
|K-Means|Spectral Clustering|Agglomerative Clustering|
|---|---|---|
|1.0|1.0|1.0|
|0.01 sec|0.53 sec|0.43 sec|
|![Kmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/04154c9a-8a0e-0f32-4397-2c79201328f1.png)|![SpectralClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/f71995fb-6a3c-9755-02fc-765e19d91975.png)|![AgglomerativeClustering.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/e2b8785f-4f77-25fd-fcfa-66c52a46c159.png)|

|DBSCAN|Birch|Mini Batch K-Means|
|---|---|---|
|1.0|1.0|1.0|
|0.12 sec|0.08 sec|0.02 sec|
|![DBSCAN.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/94ba0891-54a9-4759-3c5e-679ea3b41a1f.png)|![Birch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/f7454113-093f-71c1-b7dd-05e2757aeb6e.png)|![MiniBatchKmeans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342295/737615f6-c192-a6a3-9c65-6782cf2c4dd1.png)|

# 最後に
全部で6種類のテストに対して、6つの手法を試してみた。
K-Meansはどのテストに対しても一番早く実行が完了されていた。しかし、精度についてはいいとは言えない。
Spectral Clusteringがどのテストに対してもほとんど1.0といい精度だったが、時間が一番かかっていた。
Agglomerative Clusteringはこの6つのテストに対しては時間もかかり、精度も高いとは言えない。
DBSCANも1つ以外はうまくいってて、うまくいかなかったのは多分epsの問題だと思う。
Birchもこの6つのテストに対しては時間はあまりかかっていないが、精度は高いとは言えない。
Mini Batch K-MeansはK-Meansとあまり変わらない印象である。

色々と実装してシミュレーションすることができ、勉強になったので、別の手法でもシミュレーションしてみたい。

#参考
[scikit-learn](https://scikit-learn.org/stable/index.html#)