[ML / Code Analysis / scikit-learn] DBSCAN 코드 분석
이전부터 머신러닝을 이해하고 구현하는 능력을 키우고 싶었다. 분석할 때 급한대로 알고리즘의 작동 방식을 슥 읽고 scikit-learn의 api를 찾아서 사용하다보니 항상 뭔가 2% 부족한 것을 느꼈기 때문이다.
하이퍼파라미터는 어떻게 조절해야 성능이 올라갈까?
이 알고리즘이 동작하는데 왜 이렇게 시간이 오래 걸릴까?
논문에 나와있는 theory가 코드로 어떻게 구현이 되어 있을까?
시간을 줄이고 메모리를 효과적으로 사용하기 위해서 어떻게 구현이 되어 있을까?
이런 물음들이 주마등처럼 지나갔지만.. 막상 문제를 해결하는 그 당시에는 바빠서 이를 외면하곤 한다 ㅠ
아무리 scikit-learn api가 개발이 잘 되었다 해도 이를 겉핥기로 사용하면 한계가 있을 수밖에 없고 계속 외면하고 외면한 끝에.. 드디어 판도라의 상자를 열기로 했다!
OO님, 구현 잘 하려면 어떻게 해야해요?
같은 팀의 시니어분께 여쭤봤다.
그 분은 팀 내에서도 새로운 기술을 트래킹하시고, 이를 빠르게 구현하시기로 소문나신 분이다. 이 분은 어떻게 이런 구현의 경지(?)에 이르시게 된 것일까. 특별한 비법이 있는 것이 아닐까? 팀원분은 NLP을 하시는 분이었는데, 머신러닝이든, 딥러닝이든 근본적인 해결책은 비슷할 것 같아서 노하우를 얻고자 했다.
구현된 코드 보세요. 라이브러리 하나 정하고 보세요.
이 분은 NLP을 하시는 분이기 때문에 hugging face에서 구현된 딥러닝 모델의 코드를 모두 분석했다고 하셨다. 하긴.. hugging face을 그냥 가져다가 쓰는 사람이 단언컨대 최소 80% 이상일 것이다. 팀원분처럼 코드를 분석하고 사용하는 사람은 많지 않을 것이다. 이렇게 잘 짜여진 구현체를 분석하다보면 아래의 이점이 있다고 하셨다.
- 코드를 잘 짜는 법을 알게 된다. 알다시피, 파이썬스럽게 코딩하는 방법이 있다. 따로 책으로 나왔지만.. 실제 구현체를 보면서 파이썬스러움을 체감하는게 더욱 피부로 와 닿는다.
- 이 짓거리를 오래 하다보면, 구현체가 없는 논문을 읽었을 때 대충 어떻게 구현해야할지 감이 온다고 하셨다. 결국 코드 분석을 통해 많은 사람들이 기여한 코드를 체화함으로써, 추후에 스크래치부터 구현해야할 때 자연스럽게 그 코드 스타일이 나오는 것이다.
각설하고! 이제 본격적으로 코드 분석을 해보자.
DBSCAN 클래스 구조
class DBSCAN(ClusterMixin, BaseEstimator):ClusterMixin 클래스와 BaseEstimator을 상속한다. BaseEstimator은 scikit-learn에 있는 대부분의 estimator가 상속하는 클래스인 것 같다. 머신러닝 클래스를 위한 기본 메써드가 구현되어 있다. 파라미터 이름 반환, 피쳐 개수 반환 등의 메써드가 있다. ClusterMixin은 클러스터링 기법을 위한 기본 클래스이다. fit_predict 메써드가 기본으로 구현되어 있고, 설명에는 일관성 있는 API를 위해 존재한다고 나와 있다.
DBSCAN 클래스의 argument
| Argument 이름 | 설명 |
| eps | DBSCAN에서 core points을 판별하는데 사용되는 파라미터. 점 p가 core point인지 판별하기 위해서 dist(p,q) >= eps인 점 q가 얼마나 있는지 살펴봐야 함 |
| min_samples | 위에서 점 q가 얼마나 있는지 살펴봐야한다고 했는데, 만약 min_samples보다 더 많이 있다면, core point으로 판단. 즉, core point가 되기 위한 최소 샘플 수 |
| metric | dist(p,q)와 같이 두 점 사이의 거리를 구해야 하는데 이 때 사용하는 distance metric은 scikit-learn의 metric api를 참조 |
| metric_params | metric에 따라 부수적으로 필요한 파라미터를 넣는 argument 예를 들어서 mahalanobis metric에서는 X에 대한 inverse matrix가 필요 |
| algorithm | NearestNeighbors 모듈에 사용되는 알고리즘 |
| left_size | NearestNeighbors 모듈에 사용되는 알고리즘 중, BallTree, cKDTree에 전달되는 leaf size |
| p | minkowski metric이 사용될 때, power에 들어가는 실수 |
| n_jobs | 병렬 job을 수행하기 위한 core 개수 |
DBSCAN의 fit
DBSCAN이 작동하는 원리를 잠깐만 생각해보자. 기본적으로 어떤 점을 기준으로 선택한 metric에 따라 NearestNeighbors을 계산해야 한다.
neighbors_model = NearestNeighbors(
radius=self.eps,
algorithm=self.algorithm,
leaf_size=self.leaf_size,
metric=self.metric,
metric_params=self.metric_params,
p=self.p,
n_jobs=self.n_jobs,
)
neighbors_model.fit(X)
# This has worst case O(n^2) memory complexity
neighborhoods = neighbors_model.radius_neighbors(X, return_distance=False)NearestNeighbors 클래스의 radius argument와 DBSCAN의 eps argument은 동일한 의미를 가진다. NearestNeighbors 클래스의 radius_neighbors 메써드의 설명을 잠깐 읽고 가자.
Find the neighbors within a given radius of a point or points. Return the indices and distances of each point from the dataset lying in a ball with size ``radius`` around the points of the query array. Points lying on the boundary are included in the results. The result points are *not* necessarily sorted by distance to their query point.
어떤 점을 기준으로 radius 내에 들어오는 점들의 인덱스와 거리를 반환하는 함수이다. 타고타고 들어갔는데 .pyx 파일에서 가장 low하게 계산하는 것으로 확인됐다.
결국 인덱스와 거리를 반환하므로, 아래 코드에서는 각 점에서 eps 내에 들어오는 점들의 개수를 계산하게 된다.
if sample_weight is None:
n_neighbors = np.array([len(neighbors) for neighbors in neighborhoods])
else:
n_neighbors = np.array(
[np.sum(sample_weight[neighbors]) for neighbors in neighborhoods]
)그리고 min_samples 값과 비교하여 core samples을 뽑아낸다.
core_samples = np.asarray(n_neighbors >= self.min_samples, dtype=np.uint8)여기까지 오면 DBSCAN에서 각 점의 nearest neighbors을 계산하고, min_samples과 비교하여 core points을 추출하는 것까지 완료된다.
DBSCAN의 attributes
| Attribute 이름 | 설명 |
| core_sample_indices_ | core sample의 indices |
| labels_ | DBSCAN에 의해 붙여지는 라벨링. noise라면 -1로 표시됨 |
마무리
DBSCAN은 머신러닝 알고리즘 중에서도 이해하기 쉽운 축에 속하기 때문에 코드 분석도 어렵지 않게 끝났다. 확실히 코드 분석을 하니, DBSCAN 알고리즘의 내용이 코드의 어느 부분에 매칭이 되는지 확인을 할 수 있고 이해가 더 빠르게 되는 것 같다. 앞으로 많이 사용하는 머신러닝 알고리즘의 코드를 이렇게 분석하여 scikit-learn스럽게 구현하는 능력을 길러보자~