Scribbly

16, 17일차부터 구현한 유사 게시글 군집화(DBSCAN)에 관해 정리한 내용.

기존 기술블로그에 있던 게시글 120개 가량을 포킹하였는 바, 게시글들을 어떻게 한 눈에 분류할 지 + 기술스택별로 연관성에 따라 게시글들을 연결지을 순 없을지 고민하다가 군집 알고리즘과 지도 형태의 시각화로 구현하였다.

군집화 알고리즘

1. K-Means

K-Means Clustering | The Easier Way To Segment Your Data - displayr

k개의 중심점을 기준으로 데이터를 할당
중심점 재계산을 반복하며 수렴

단점: 독특한 개체(이상치)도 군집화에 포함되는 단점

K-Means 알고리즘 작동방식

개체들 사이에 k개의 점을 둔다
각 개체들을 가장 가까운 점과 연결한다.
점들을 자신와 연결된 개체들의 위치의 평균으로 이동시킨다
2와 3을 반복하며 수렴할 때까지 반복한다.

2. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

데이터 포인트 주변 eps 반경 내에 minPts 이상이 있으면 하나의 클러스터로 정의
이상치(노이즈)는 자동으로 분리됨
복잡하고 모양이 다양한 클러스터에 강함

단점: eps와 minPts 튜닝에 민감

DBSCAN 알고리즘 작동방식

DBSCAN Clustering – Explained - Towards Data Science

minPts는 군집에 포함되어야 하는 최소 개체, eps는 군집의 반경이다.
각 개체마다 eps 반경 안에 몇 개의 개체가 포함되는지를 계산한다.
1. 위에서 빨간색 A 개체들은 eps내에 4개의 개체가 인접하여 있어 minPts를 충족하는 개체들이다.
2. 노란색 B개체들은 그 자체로는 eps내에 minPts를 중족시킬 만큼의 충분한 개체들이 없으나, A개체들과는 인접하여 있다. 즉 노란색 B개체들은 군집의 경계이다.
3. 파란색 N개체는 eps내에 minPts를 충족시킬 만큼의 개체도 없고, 군집과도 인접하여 있지 않다. 즉 파란색 N 개체는 노이즈이다.
minPts를 작게하면 작은 개체들도 군집으로 평가된다. 즉 잡음도 하나의 군집으로 평가될 수 있다.
eps를 너무 크게하면 군집이 별도로 나뉘어지지 않고 하나의 큰 덩어리로 평가된다. 또한 잡음들도 군집에 포함되게 된다.
반면 너무 큰 minPts나 너무 작은 eps는 인접한 개체를 찾지 못해 군집 형성 조건 자체를 중족시키지 못한다.

3. HDBSCAN (Hierarchical DBSCAN)

DBSCAN의 확장. 밀도 기반 + 계층적 군집 + 자동 튜닝
- eps에 기반하여 클러스터링하는 DBSCAN 방식과 다르게 다양한 계층에서 클러스터링하며 stability가 높은 군집만 형성함
다양한 밀도를 갖는 클러스터도 잘 분류함
작은 클러스터도 잘 감지하며 이상치 탐지에도 강력

단점: Python 중심 구현

HDBSCAN 알고리즘 작동방식

How HDBSCAN Works - hdbscan

프림 알고리즘을 통해 개체 간 거리를 기준으로 한 최소 신장 트리를 구축한다.
최소 신장 트리에서 distance 큰 간선들부터 제거한다. 개체들간의 연결과 분리를 union-find 알고리즘으로 추적해나간다.
군집의 크기가 변경되는 정도를 추적해서 min_cluster_size보다 더 큰 크기가 변경된 경우가 새로운 군집을 생성한 시점으로 본다. 이를 바탕으로 아래와 같이 압축된 트리를 만든다.
압축된 계층 구조의 leap 노드가 곧 HDBSCAN의 군집이 된다. (아래의 그림에서 밀도가 높은 파란색 원 군집과 상대적으로 밀도가 낮은 빨간색 원 군집이 생성되었다.)

DBSCAN 방식과 비교한 주된 이점은 위치별로 개체들 사이의 밀도가 달라도 이를 군집화할 수 있다는 것이다.
HDBSCAN vs. DBSCAN - Daily Dose of Data Science

다단계 eps를 이용한 dbscan 군집화

hdbscan에 적합한 node.js 라이브러리를 찾지 못하여 dbscan으로 진행하였다.

dbscan과 관련하여 테스트를 할 때에 아래와 같은 이슈가 발생하였다.

엡실론이 0.4 이상 넘어가는 경우 55개 게시글이 하나의 군집으로 묶이는 현상이 발생하였다. Next.js 관련 게시글부터 React까지가 하나의 군집으로 형성되는 것이다. (이러한 현상은 hdbscan에서도 동일하게 발생했을 것)
반대로 앱실론이 0.35 미만으로 떨어지는 경우, 40개 미만의 게시글만 군집을 형성하고 나머지 80개 게시글은 노이즈로 처리되었다.

따라서 아래와 같은 방향으로 다단계 eps를 처리하였다.

eps 0.33부터 순차적으로 0.34, 0.35로 증가하며 군집화를 진행한다. <- 군집된 게시글은 12, 5, 5 정도로 일정 비율을 유지하였다.
이후 0.37, 0.39, 0.41, 0.44, 0,48... 과 같이 간격을 조금씩 넓혀가며 0.75까지 군집화를 진행한다.
일찍 군집화되었을수록 게시글 간의 간격이 촘촘하고 고품질이라는 의미이므로 점수를 높게 준다.

이렇게 하는 경우 같은 분야의 게시글이어도 여러 개의 군집으로 나뉘는 특징이 있으나, Next.js만 55개 묶이는 것보다는 적정 게시글 숫자를 유지하였다. 또, 특별한 품질이나 기준 없이 묶이는 K-means 클러스터링보다 동적으로 군집이 형성되는 특징이 있다.

군집 요약 및 라벨링 (chatGPT)

이렇게 군집화된 게시글들을 symentic하게 라벨링하는 것은 chatGPT로 한다.

chatGPT에게 해당 군집의 게시글들의 요약들을 모두 넘겨주고,

군집의 이름, 요약, 키워드를 반환하도록 지시한다.

  const obj = {
    title: "PWA 개발",
    summary:
      "이 군집은 Next.js와 Firebase를 활용한 PWA 웹앱 개발 과정을 다룹니다.",
    tags: "[pwa, next js, firebase, quiz]",
  };

군집의 summary는 text-embedding-3-small을 통해 벡터화 한다.

군집 간 유사도 비교

벡터화된 군집 요약을 바탕으로 군집 간 유사도를 비교한다.

즉 군집을 생성하고, 군집에 걸맞는 요약을 생성하고, 해당 요약의 벡터를 이용해 군집 간 유사도를 비교한다.

[post1]  \
[post2]   -> cluster 1  -> symentic vector → similarity with cluster 2: 0.81
[post3]  /

[post4]  \
[post5]   -> cluster 2  -> symentic vector → similarity with cluster 1: 0.81

데이터 시각화

main/components/cluster/graph/cluster-graph-app.tsx

그래프 시각화는 d3를 이용한 svg로 한다.

문제는 d3를 시각화 할 때에는 DOM 객체가 필요한데, JSDOM을 통해 데이터를 DOM 형식의 string으로 반환할 수 있다. SSR로 d3.js 그래프 그리기. - 브런치

main/components/cluster/graph/cluster-graph-svg.tsx 에서 컴포넌트를 JSDOM으로 렌더링하고, innerHTML로 삽입하여 SSR로 캐싱한다.

main/components/cluster/graph/cluster-graph-hydrator.tsx 에서 클라이언트 사이드 렌더링을 한다. 아래와 같으 svgEl를 찾아 이벤트 헨들러를 넣어준다.

  useEffect(() => {
    const svgEl = document.querySelector("#cluster-graph") as SVGSVGElement;
    if (!svgEl) return;

...

      group.addEventListener("click", () => {
        setSelectedCluster(matchedNode);
      });
    });

    return () => {
      groups.forEach((group) => {
        group.replaceWith(group.cloneNode(true));
      });
    };
  }, [nodes, setSelectedCluster]);

이렇게 만들어진 지도는 main/app/map/page.tsx 에서 게시글 목록과 함께 보여진다.
1. 지도의 노드를 클릭하면 해당 군집의 게시글이 게시글 목록에 나타난다.
2. 반대로 게시글 목록에서 군집명을 클릭하면, 지도에서 해당 군집의 노드를 zoom한다.

이렇게 만들어진 지식 지도는

밀집도가 높은 군집은 투명하지 않고 선명하게 표현된다.
그리고 밀집도가 낮은 군집들이 중간 중간 배치되어 있다.
군집들 간의 긴밀성(코사인 유사도)가 높을수록 굵은 간선으로 표시된다.
Noise라 할 수 있는 "Node.js 비동기 처리" 부분이 별도의 군집을 형성하고 있고, 알고리즘과 관련된 부분, Next.js와 관련된 부분이 서로 분리되어 큰 군집을 형성하고 있다.

scribbly.