이번에 대회를 준비해보면서 데이터에 이상치가 존재한다고 판단되는데 이상치를 판단하는 기준을 iqr이 아닌 다른 방법을 조사해 보는중 군집분석을 통해서 이상치를 판단할 수 있다는 것을 알게 되었다. DBSCAN에 대해 공부한 내용을 토대로 정리해보고자 한다.
DBSCAN(Density-Based Spatial Clustering of applications with noise)
DBSCAN은 밀도 기반 비지도 학습이다. 한 공간에서 수많은 점이 있다고 가정한 경우, 낮은 밀도를 가진 지역에 있는 점들은 outlier로 판단한다. 이제 그 과정에 대해 살펴보도록 할 것이다.
Hyperparameter
hyperparameter로는 Epsilon과 Minpoint가 있다.
Epsilon은 한 쌍의 점들 사이의 유클리디안 거리로 간략하게 설명하면 반경이라고 생각하면 된다. 만약, 두 점 사이의 거리가 epsilon보다 작거나 같은 경우, 두 점은 neighbor로 판단된다.
Minpoints는 dense cluster를 형성하는데 필요한 최소한의 point 수이다. 즉, 반경(epsilon) 내에 특정 이상의 점들이 존재해야 한다. 예를 들어, Minpts=4는 dense cluster를 형성하기 위해서는 반경 내에 최소한 4개 이상의 점들이 필요하다는 것을 의미한다.
Points
점은 크게 Core points와 Border Point로 나눌 수 있다.
Core point는 core point의 epsilon-neighborhood안에 그 점까지 포함하여 minpts 개수 이상인 점을 의미합니다. 만약, p라는 점이 있다고 가정하면, p점의 epsilon neighborhood 안에 Minpts 개수 이상이면 p는 core point이다. Border point는 core point는 아니지만 core point의 neighborhood 안에 있는 점을 의미한다. 즉, 밀집된 지역 근처나 경계에 존재하는 점이다. Noise Point는 어떤 dense clusters에도 속하지 않는 점이다.
DBSCAN algorithm을 이해하기 위한 3개의 용어에 대한 이해 필요
1. Direct Density Reachable
: a point "p" is directly density reachable from another point "q"
- p는 q의 eplison neighborhood 안에 존재해야 하며 core point인 q의 eplison neighborhood 안에는 Minpts 이상의 점이 있어야 한다.
- 이의 경우, p는 q로부터 directly density reachable 되어 있다고 한다.
2. Density Reachable
: a point "p" is density reachable from "q" if there are a set of core points leading from "q" to "p"
- 그림 (a)를 참고해서 보면, p1은 q로부터 directly density reachable하고, p는 p1으로부터 directly density reachable하다. p는 q의 epslion neighborhood 안에 존재하지 않기 때문에 p는 q로부터 directly density reachable하지 않다. a chain of points p1이 q로부터 directly density reachable하지 때문에 p는 q로부터 density reachable하다.
3. Density-Connected
: two points "p' and "q' are density connecte if there are a core point "o", such that both "p" and "q" are density reachable from "o".
p와 q는 border point이다. p는 o로부터 density-reachable하고 q는 o로부터 density-reachable하다. 이와 같은 경우를 p와 q는 density connected하다고 한다.
A Density-Cluster는 density connected points의 group으로부터 만들어진다.
DBSCAN Algorithm
- input : N objects to be clustered and global parameter epslion & Minpts
- output : Cluster of object
- 점 p를 임의로 지정
- epslion & Minpts와 관련해서 p로부터 density-reachable한 점을 찾는다.
- 만약, p가 core point라면 cluster가 형성되어진다.
- 만약, p가 border point이면, p로부터 density-reachable한 점을 찾지 않고 DBSCAN은 데이터 베이스의 다음 점을 방문한다.
- 이 과정은 변화가 없을 때까지 계속되어진다.
Code
sklearn.cluster.DBSCAN(eps=0.5, *, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=None)
Parameter
- eps : 반경(default=0.5)
- min_samples : epslion neighborhood 안에 들어갈 최소한의 point 개수(default=5)
- metric : feature 배열 사이의 거리 방법(default='euclidean') -> {'eculidean', 'manhatten', 'chebyshev', 'minkowski', 'wminkowski', 'seuclidean', 'mahalanobis'}
- algorithm : 최근접 이웃을 찾는 알고리즘{'auto', 'ball-tree', 'kd_tree', 'brute'} -> NearstNeighbors 모듈 방법 선택(default = 'auto')
- brute force : 모든 쌍의 거리를 계산하여 탐색
- KD Tree : 트리 구조를 사용해서 모든 거리를 계산하지 않고 비용을 줄여 탐색
- Ball Tree : KD Tree와 마찬가지로 트리 구조를 사용. 트리를 만드는 비용은 크지만 고차원의 데이터에서 KD Tree보다 좋은 성능으로 탐색
- 위의 algorithm 방법을 통해 각 데이터의 근접 이웃의 개수를 셈으로써 Core point 여부를 결정하다.
Methods
fit(X, y=None, sample_weight=None)
fit_predict(X, y=None, sample_weight=None)
get_params(deep=True)
set_params(**params)
참고자료
https://en.wikipedia.org/wiki/DBSCAN
http://www.sthda.com/english/wiki/wiki.php?id_contents=7940
https://www.digitalvidya.com/blog/the-top-5-clustering-algorithms-data-scientists-should-know/