계층적 군집화(hierachical clustering) [파이썬]

1. 계층적 군집화란?

계층적 군집화는 데이터를 계층적으로 클러스터링하는 방법으로, 데이터 포인트를 유사성에 따라 클러스터로 그룹화합니다. 이 방법은 군집의 계층적 구조를 형성하며, 덴드로그램(dendrogram)을 통해 클러스터의 병합 과정을 시각적으로 표현할 수 있습니다.

2. 계층적 군집화의 유형

계층적 군집화는 크게 두 가지 유형으로 나눌 수 있습니다:

• 단일 링크 (Single Linkage): 두 클러스터 간의 거리를 두 클러스터 간의 가장 가까운 거리로 정의합니다. 이는 "최단 거리 연결" 방법이라고도 불립니다.
• 완전 링크 (Complete Linkage): 두 클러스터 간의 거리를 두 클러스터 간의 가장 먼 거리로 정의합니다. 이는 "최장 거리 연결" 방법이라고도 불립니다.
• 평균 링크 (Average Linkage): 두 클러스터 간의 거리를 클러스터 내 모든 포인트 쌍 간의 평균 거리로 정의합니다.
• 중심 링크 (Centroid Linkage): 두 클러스터 간의 거리를 각 클러스터의 중심 간의 거리로 정의합니다.

3. 계층적 군집화의 단계

1. 초기화: 각 데이터 포인트를 개별 클러스터로 시작합니다.
2. 거리 계산: 모든 클러스터 간의 거리를 계산합니다.
3. 클러스터 병합: 가장 가까운 두 클러스터를 병합합니다.
4. 반복: 클러스터의 수가 원하는 개수에 도달할 때까지 2-3단계를 반복합니다.

 

소스코드

초기단계

각 점을 싱글 클러스터에 넣는다

 

단계 1

클러스터간 모든 유클리드 거리 계산 

 

단계 2

2개의 가장 유사한 클러스터를 합병

max-link

min-link

average-link

위 3가지 방식중 하나 사용

 

종료 조건

하나의 단일 클러스터가 생성되면 종료 -> 사용자 지정 가능

#계층적 군집 방법
import math
CarData = {         #초기 데이터 셋
'A' : [2.5,2.5],
'B' : [2.25,2],
'C' : [3,2],
'D' : [2.5,1.75],
'E' : [0.25,1],
'F' : [0.5,0.5],
'G' : [0.25,0.25],
'H' : [-0.25,0.5],
'I' : [-0.25,-0.25],
'J' : [0.25,-0.5],
'K' : [-2,-1.5],
'L' : [-1.5,-1.75],
'M' : [-2.5,-2],
'N' : [-2,-2.25],
'O' : [-2.5,-2.5]
}

count =0   #전체 카운트 횟수

def makeSingleton(data):   #데이터 셋을 가지고 싱글톤 클러스터 생성 함수
    singleton = []
    key_list = list(data.keys())
    for x in range(len(key_list)):
        singleton.append(tuple(key_list[x]))
    return singleton

carcluster = makeSingleton(CarData)

def minLinking():    #각 클러스터 끼리 minLink를 계산하여 병합하는 함수
    resultDict ={}   #클러스터들 끼리 minLink 계산후 그값 저장할 딕셔너리
    for x in carcluster:   # (c1클러스터-c2클러스터) : x, 이런식으로 비교군과 그값을 저장 
        for z in carcluster:
            if(x==z):     #같은 클러스터를 비교할 시
                continue  #값은 0이므로 건너 뜀
            if (z, x) in resultDict:  #(A-B) 비교, (B-A) 비교는 값이 같으므로
                continue              #건너 뜀
            resultDict[(x,z)] = minLink(x, z) #두 클러스터 사이의 minLink를 계산
    a = min(resultDict, key=resultDict.get)  #전체 클러스터들 끼리 계
    
    print("%d 번 수행 병합되는 클러스터" %(count))
    print(a)  #합쳐진 클러스터 출력

    for y in a:      #기존 클러스터에서 합쳐진 각 클러스터 제거
        carcluster.remove(y)
    newSet = []
    for k in a:
        for r in k:
            newSet.append(r)  
    carcluster.append(tuple(newSet))  #합쳐진 클러스터 새로 추가
    print("클러스터 목록");
    print(carcluster)                 #수행 후 클러스터 목록 출력
   

def minLink(carcluster1, carcluster2):   #실제로 minLink를 계산하는 함수
    minValue = []   
    for x in carcluster1: #A,B,C         두 클러스터에 포함된 모든 벡터간 유클리드거리 계산
        for z in carcluster2:  #D,E
            minValue.append(Eudist(CarData[x], CarData[z]))  
    return min(minValue) #그 거리중 최솟값 저장, 어짜피 계산은 최솟값만 비교하기에.
   

def Eudist(frontSet, secondSet):    #두 벡터간 유클리드 거리를 계산하는 함수
    result = 0
    for i in range(len(frontSet)):
          x1 = frontSet[i]
          x2 = secondSet[i]
          result += (x1-x2)**2
    return (math.sqrt(result)) 

while(True):    #결과 출력
    if(len(carcluster)>2):
        print("---------------------------------------------------------------------------------------------------")
        minLinking()
        print("---------------------------------------------------------------------------------------------------")
        count = 1+count
    else:
        break

 

 

덴드로그램