JupyterでDBSCANのメリットを確認してみた

DBSCANのメリットを可視化して確認してみました。

## DBSCANとは
最も一般的なクラスタリングアルゴリズムの一つで、データ点の密度を基に分類します。
パラメータはeps(ε)、minPtsの2つ。
各データ点は下記のロジックでコア点・(密度)到達可能点・外れ値に分類されます。
>- 点 p がもし、p を含め、距離 ε(ε は p からの近傍の最大半径)以内に少なくとも minPts の点があれば、その点はコア点である。
- 点 q がもし、各 pi+1 が pi から直接到達可能(パス上のすべての点は、 q の可能な例外を持つ、コア点で無ければならない。)な、p1 = p かつ pn = q であるパス p1, ..., pn があれば、q は p から到達可能である。
- 他のどの点からも到達可能でないすべての点は外れ値である。

> [DBSCAN - Wikipedia](https://ja.wikipedia.org/wiki/DBSCAN)

密度ベースのため
・球（超球）の形状を前提としない
・ノイズを分離できる
といったメリットがあり、例えばk-meansでは難しいこんなデータでも上手く分類可能（なはず）です。
![output_6_1.png](https://qiita-image-store.s3.amazonaws.com/0/335227/6a7c5fb8-a493-6793-bf1c-0a245aa4a0ee.png)

また、k-meansのようにクラスタ数を指定する必要はありません。

[（詳しい英語記事）](https://medium.com/@elutins/dbscan-what-is-it-when-to-use-it-how-to-use-it-8bd506293818)

それではjupyter labで実際にクラスタリングしてみます。

## 例

ライブラリの読み込みとグラフの表示設定。scikit-learnを使います。

In[1]:

```python
import pandas as pd
import numpy as np
import matplotlib as mpl
import seaborn as sns
from sklearn.cluster import DBSCAN
%matplotlib inline
sns.set()
```
datasetの読み込み。

In[2]

```python
file = 'Dataset_Compound.csv'
df = pd.read_csv(file)
```
DBSCANの実施。
* eps(ε) = 0.1~5
* minPts = 5~30
の範囲で探索し、結果をDataFrameに入れてみます。

In[3]

```python
columns=['eps','minPts','cluster_index','cluster_size']
df_dbscan = pd.DataFrame(columns=columns)

for eps in range(1,51):
    eps /= 10
    for minPts in range(5,31,5):
        dbscan = DBSCAN(eps=eps,min_samples=minPts).fit(df)
        labels = dbscan.labels_
        clusters_index = np.unique(labels) #index of clusters, '-1' indicates noize points
        clusters_size = np.bincount(labels+1) #size of each cluster
        result = [eps, minPts, list(clusters_index), list(clusters_size)]
        df_dbscan.loc[len(df_dbscan)] = result
```

クラスタ数6以上、ノイズ100未満の結果に絞って表示。

In[4]

```python
filt = df_dbscan[columns[2]].map(lambda x: len(x)>5)
filt = filt & df_dbscan[columns[3]].map(lambda x: x[0]<100)
df_dbscan[filt]
```

Out[4]

<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>eps</th>
      <th>minPts</th>
      <th>cluster_index</th>
      <th>cluster_size</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>54</th>
      <td>1.0</td>
      <td>5</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[97, 92, 15, 21, 158, 16]</td>
    </tr>
    <tr>
      <th>60</th>
      <td>1.1</td>
      <td>5</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[91, 92, 18, 24, 158, 16]</td>
    </tr>
    <tr>
      <th>66</th>
      <td>1.2</td>
      <td>5</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[85, 92, 22, 26, 158, 16]</td>
    </tr>
    <tr>
      <th>72</th>
      <td>1.3</td>
      <td>5</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[74, 92, 27, 32, 158, 16]</td>
    </tr>
    <tr>
      <th>73</th>
      <td>1.3</td>
      <td>10</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[90, 92, 20, 23, 158, 16]</td>
    </tr>
    <tr>
      <th>78</th>
      <td>1.4</td>
      <td>5</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[64, 92, 28, 41, 158, 16]</td>
    </tr>
    <tr>
      <th>79</th>
      <td>1.4</td>
      <td>10</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[87, 92, 21, 25, 158, 16]</td>
    </tr>
    <tr>
      <th>84</th>
      <td>1.5</td>
      <td>5</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[59, 93, 31, 42, 158, 16]</td>
    </tr>
    <tr>
      <th>85</th>
      <td>1.5</td>
      <td>10</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[83, 93, 22, 27, 158, 16]</td>
    </tr>
    <tr>
      <th>86</th>
      <td>1.5</td>
      <td>15</td>
      <td>[-1, 0, 1, 2, 3, 4]</td>
      <td>[99, 92, 15, 21, 156, 16]</td>
    </tr>
  </tbody>
</table>
</div>


上手く分類できていそう。
78番目をグラフで確認してみます。

In[5]

```python
index = 78
eps = df_dbscan[columns[0]][index]
minPts = df_dbscan[columns[1]][index]
dbscan = DBSCAN(eps=eps,min_samples=minPts).fit(df)
labels = dbscan.labels_
X = df.copy()
X['labels'] = labels
X['color'] = X.labels.map(lambda x: 'noize' if x<0 else 'r'+str(x)) #色分けのためにcategorical dataを作成
X.sort_values('color')
sns.scatterplot(x='x', y='y', data=X, hue='color')
```

Out[5]
![output_9_1.png](https://qiita-image-store.s3.amazonaws.com/0/335227/afecb571-3106-5bc2-b9ba-d4060a9454c0.png)

右側：ノイズを上手く切り分けられています。
左下：ドーナツ型（紫）とその内部（茶）を上手く切り分けられています。
左上：他のクラスタと密度に違いがあり、周囲がノイズと判定されています。

## まとめ

DBSCANの下記のメリットが確認できました。

- 球（超球）の形状を前提としない
- ノイズを分離できる
- クラスタ数の指定が必要ない

反対に、デメリットには下記が挙げられるようです。

- クラスタの密度に差が大きいと上手くクラスタ分けできない  
eps, minPtsのパラメータで全クラスタの密度を決めるからですね。  
階層クラスタリングによる解決がありえます。
- 計算コストが高い  
全データ点を対象とした計算を反復して行うため。  
今回程度の計算量では気になりませんが、次元の増加に弱い、リアルタイムのアプリケーションには実装しにくいなど言われています。




Dataset References: 
**Compound**: _C.T. Zahn, Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Transactions on Computers, 1971. 100(1): p. 68-86._