[Data Engineering] Data Mining (K-means clustering)

📌 목차

• Data Mining 
• K-Means Clustering

 

Data Mining 알고리즘 중에서 K-means clustering을 하둡 MR로 어떻게 구현할지 설명한다.

🍀 Data Mining 

데이터 마이닝은 데이터로부터 이미 알려지지 않은, 그러나 잠재적으로 유용한 정보를 추출하는 작업이다. 의미 있는 패턴을 발견하기 위해, 자동 혹은 반자동 기술을 사용해 대용량 데이터를 탐색 및 분석하는 작업이다. 

🔅 데이터 마이닝으로 볼 수 없는 것은?

• sql로 DB에 쉽게 접근해 데이터를 조회하는 류의 작업들

🔅 데이터 마이닝으로 볼 수 있는 것은?

• 특정 성씨가 특정 지역에서 보다 빈도 수가 높은 경우를 찾는 것
• 검색 엔진에서 검색된 문서들을 문맥에 따라 그룹핑 하는 것
• 예, 삼성전자로 검색하여 결과를 제품소개, 서비스, 주식 별로 그룹핑함

🔅 데이터 마이닝 기술 분류

• 연관규칙
• 분류
• 클러스터링
• 기타 (순차검색, 회귀분석, 이상치 탐색)

🔅 데이터 마이닝 작업

• 예측 방법
  • 주어진 변수의 모르는 값이나 미래의 값을 다른 변수를 사용하여 예측
  • 예, 과거 주식 데이터를 분석해 내일의 주식 방향을 예측
  • 분류, 회귀 분석, 이상치 검출
• 서술 방법
  • 주어진 데이터를 설명하는 패턴을 찾아냄
  • 예, '기저귀와 맥주는 함께 잘 팔린다'는 규칙을 찾아냄
  • 클러스터링(비슷한 것끼리 묶는 것), 연관 규칙, 순차 패턴

 

🍀 K-Means Clustering

이 알고리즘의 input은 k이다. k는 k개의 cluster로 임의의 데이터를 분류해달라는 것이다. 1,2번은 초기화 작업이고 2,3,4번이 반복 수행되는 작업이다.

1. 임의의 데이터를 k개의 비어있지 않은 subset으로 분류를 한다. 
2. k개의 subset에서 중점을 구한다. 처음엔 랜덤하게 k개의 중점을 미리 만들어놓고 시작한다.
3. 각 object에 대해서 가장 가까운 중점을 찾아서 해당 클러스터에 배치한다. 가장 가까운 중점 그룹으로 편입된다. 기존 알려져 있는 중점을 기준으로 클러스터가 형성이 된다. 그 후 다시 2번으로 돌아와서 새롭게 형성된 클러스터를 기준으로 중점을 만든다. 그럼 k개의 중점이 다시 업데이트된다. 그리고 다시 새롭게 모든 object에 대해 클러스터 생성하고 중점 갱신하는 작업을 반복적으로 한다.
4. k개의 중점에 전체적인 변화가 없다면 종료한다. 종료했을 때의 클러스터가 우리가 원하는 클러스터로 형성되는 것이다. 

 

k=2

K-Means 클러스터링 알고리즘 수행 예시이다. 랜덤하게 a, b로 들어간 것이다. 그리고 각 클러스터의 중점을 구한다. 이렇게 임의의 클러스터 배치 후 구할 수도 있지만, 사실 임의의 문제 범위에서 랜덤하게 두 점을 선택해도 크게 상관없다. 

중점 2개에 대해서 모든 점에 대해 다시 클러스터링을 한다. 주어진 점들을 보면서 다시 가까운 중점 그룹에 들어간다. 아까와 클러스터링 결과가 달라진다. 랜덤하게 (5,5)가 a에 있었는데 이제는 b에 배치된다. 새롭게 분류가 되었기 때문에 중점을 다시 갱신한다. 이 과정을 계속 반복하게 되면 어느 순간 중점의 값이 변하지 않게 된다. 그럼 클러스터링 알고리즘의 수행을 멈추고 종료 시점 결과가 최종 결과가 된다.

어느 중점에 더 가까운지 표현할 때 쓰는 함수 distance()가 있는데 이건 거리이다. 문제 도메인에 따라서 이 함수가 달라질 수 있다. 거리 함수에 따라서 알고리즘이 조금씩 변화될 수 있다. 지금은 동일하게 x축 거리와 y축 거리가 모두 같은 등급인데, 예시로 아파트 가격과 역세권 거리를 두고 생각하게 되면 가격은 수천만원 차이가 나고 거리는 수 키로 차이가 난다. 가격은 실체 억단위고 거리는 키로미터라서 일의 자리 수로 움직인다. 거리에 위와 같은 식으로 적으면 가격에 따라 임팩트가 더 크게 된다. 따라서 distance()를 달리 하는 방식으로 K-Means 클러스터링을 고도화해서 사용해야 한다. 

 

Map

• Main에서 broadcast된 k개의 center 정보를 읽음 (setup)
• input file로부터 input point를 읽음
• k개의 center 중에서 input point와 가장 가까운 center를 찾아서 (center_id=cluster_id, input point) 쌍을 emit

Reduce

• 각 center_id를 기준으로 모인 input point 벡터를 이용하여
• 새로운 center를 계산하여 (center_id, new center point)를 emit

Main

• 랜덤하게 k개의 center point를 생성하고 이 점들을 broadcast -> config 객체로
• MR 작업 시작
• 결과 파일을 읽어서 새로운 center point를 broadcast 한 후에 2번 작업 수행. 새로운 center point가 직전 단계의 center point와 차이가 없으면 종료

 

center 0에 더 가까우면 key를 0으로 하고 point를 value로 내보낸다. 그리고 shuffle로 같은 key를 갖는 점들끼리 value list를 만든다. 새롭게 계산된 클러스터가 0번은 3개, 1번은 4개라는 것이다. reduce에서는 새로운 center를 구하고 output으로 만든다. 다음 MR에서는 다시 점들은 map으로 broadcast 해주면 된다. 그리고 반복적으로 작업을 수행한다.