Clustering - Hungrian Algorithm

Clustering 은 주어진 데이터를 정해진 수의 군집 수에 따라 비슷한 특성끼리 묶어주는 알고리즘으로 K-Means, DBSCAN, deep learning based clustering 등 모든 종류의 clustering 알고리즘은 훈련 후의 각 데이터 샘플 별 할당된 군집 번호를 출력합니다. 하지만 문제는 할당된 군집 번호가 훈련 시마다 매 번 다르고 각 데이터 별 라벨이 있을 경우 라벨 번호와 맞지 않는다는 것인데요, 이번 포스트에서는 clustering 이후의 군집 번호를 기준 (라벨)에 맞게 재정렬하는 Hungarian 알고리즘에 대해 알아보도록 하겠습니다.

4개의 클래스를 가진 16개의 데이터가 [0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3] 라벨을 가졌을 때, clustering 결과가 [1,1,1,2,2,2,2,3,3,3,3,3,0,0,0,0] 이 나왔다고 가정해봅시다. 그렇다면 이 clustering 결과는 라벨고 하나도 맞지 않으니 정확도는 0일까요? 당연히 아닙니다. Clustering 알고리즘의 성능을 평가하기 위해서는 clustering 군집 번호를 라벨과 최대한 맞도록 재정렬하는 과정이 필요하고 그 과정에서 쓰이는 알고리즘이 바로 Hungarian 알고리즘입니다. 여기서는 clustering 의 군집이 {1:0, 2:1, 3:2, 0: 3} 으로 다시 할당되어야 하겠죠. 

Hungarian algorithm

Hungarian 알고리즘은 두 개의 그래프에서 정점 간 이동할 때 발생하는 cost 를 최소화하는 문제로 한 그래프의 정점 $i$에서 다른 그래프의 정점 $j$로 갈때의 cost 테이블 $C[i,j]$를 기반으로 동작합니다. 즉, 한 그래프의 정점들은 $C$의 행으로 표현되고 다른 그래프의 정점들은 $C$의 열로 표현되면서 각 행과 열 별로 cost 합이 최소가 되는 매칭 인덱스를 찾는 것이죠. 다음과 같이 회사 3개에 따른 Musition/Chef/Cleaners 고용 비용에 대한 cost 테이블을 예로 들어보겠습니다. 하나의 회사가 셋 중 하나만을 고용할 수 있고 각 회사의 고용비를 합쳤을 때 언제 최소가 되는지 찾는 문제입니다.

Steps

먼저 처음 cost table 에서 각 행의 최소값을 각 행에 대해 빼줍니다.

이후에는 각 열의 최소값을 각 열에 대해 빼줍니다.

이제 0을 가진 행과 열에 대해 라인을 그려줍니다.

라인이 2개 생겼습니다. 우리는 3대3 매칭을 찾아야 하기 때문에 매칭하는 추가적인 과정이 더 필요합니다. 그린 라인에 포함되지 않는 원소 중 가장 작은 원소를 라인에 완벽히 지워지지 않은 행에 대해 빼줍니다. 여기서는 2를 첫 번째, 세번째 행에 대해 빼줍니다.

이후 라인에 포함되지 않은 가장 작은 원소인 2를 라인에 완벽히 포함된 열에 더해 보상합니다.

이제 다시 0이 포함된 행과 열에 대해 라인을 그려줄 차례입니다.

이제 라인이 3개 생겼으므로 재할당을 시도할 수 있습니다. 재할당은 테이블에서 행, 열 당 각각 1개씩 0이 생기는 조합으로 구성됩니다.

만약 라인의 개수가 정점의 개수보다 적다면 추가적인 매칭 과정을 반복적으로 수행하면 됩니다. 결과적으로 Company A는 cleaner, Company B는 chef, Company C는 musician을 고용하면 됩니다. 알고리즘을 간단히 살펴봤을 때 결국 cost를 최소화하는 매칭조합을 찾는 것이니 각 행,열마다 최소값을 찾아 빼주는 과정을 반복하면서 0의 위치에 따라 알고리즘의 진행 여부를 결정합니다.

위의 예에 대해 Hungarian 알고리즘이 찾은 매칭이 실제로 cost 를 최소화하는 매칭인지 총 $3\times 2\times 1=6$가지 경우에 대해 cost를 계산해볼 수 있습니다. Hungarian 알고리즘이 찾은 매칭의 cost가 407로 모든 경우 수에 비해 가장 작습니다.

Clustering

Clustering 에도 유사하게 적용할 수 있습니다. 실제 라벨 (기준)를 하나의 그래프 정점으로 clustering 군집 결과를 다른 그래프의 정점으로 두어 각 데이터로부터 cost 테이블 $C$을 구성한 후 Hungarian 알고리즘을 수행하면 clustering 군집 번호를 기준에 맞게 재할당 할 수 있습니다. 예를 들어 16개의 데이터가 [0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3] 라벨을 가졌을 때, clustering 결과가 [1,1,1,2,2,2,2,3,3,3,3,3,0,0,0,0] 나온 경우에 대해서 $C[0,1]=3. C[1,1]=1, C=[1,2]=3... $등으로 $C$를 구성할 수 있다는 것이죠. 이때 주의할 점은 이와 같이 $C$를 구성할 경우에는 라벨과 cluster 가 최대한 잘맞는 최대화 문제가 되버리기 때문에 최소화 문제로 바꾸어야 한다는 점이죠.

파이썬에서는 scipy.optimize 모듈의 linear_sum_assignment 함수로 구현되어 있습니다. linear_sum_assignment 함수를 수행하면 매칭되는 행 인덱스와 (row_ind) 열 인덱스가 (col_ind) 출력되며 행 인덱스는 항상 0부터 순서대로 정렬되어 출력됩니다. 밑의 코드에서 $w$는 $C$를 뜻하며 $-w$를 통해 최소화 문제로 바꿉니다. 이후 최종적으로 cost와 기준 라벨 (ref_indices)와 clustering 군집 번호 (pred_indices) 간의 매칭 딕셔너리를 구할 수 있습니다.

def get_matching_indices(ref_indices, pred_indices, n_clusters=num_clusters): 
    ## Check both indices are type of numpy array
    assert isinstance(ref_indices, np.ndarray) and isinstance(pred_indices, np.ndarray)
    ## Check both indices have same length
    assert len(ref_indices) == len(pred_indices)
    ## Convert both indices to numpy integer
    ref_indices = ref_indices.astype(np.int64)
    pred_indices = pred_indices.astype(np.int64)
    
    w = np.zeros((num_clusters, num_clusters), dtype=np.int64)
    for i in range(ref_indices.size):    
        w[ref_indices[i], pred_indices[i]] += 1

    from scipy.optimize import linear_sum_assignment as linear_assignment
    row_ind, col_ind = linear_assignment(w.max() - w)
    ind_dict = {}
    for j in range(n_clusters):        
        index = np.where(col_ind == j)
        i = row_ind[index]
        ind_dict[int(np.squeeze(i))] = j
    
    cost_matrix = w.max() - w
    cost = cost_matrix[row_ind, col_ind].sum()

    return cost, ind_dict

만약 clustering 시 기준이 될 수 있는 라벨이 없을 경우 앙상블을 위해 여러 번 clustering 하여 하나의 결과를 기준 값으로 삼을 수도 있습니다. 다음 코드는 여러 번 돌린 군집 결과를 담은 preds_matrix 에 대해 첫 번째 군집 결과를 기준으로 잡고 이후 군집 결과에 대해 Hungarian algorithm 을 수행하여 기준 군집 결과에 대해 다른 군집 번호를 재할당 하는 코드입니다.

def indices_matching(preds_matrix):
    ref = preds_matrix[0]
    ## Generate new matrix to store ordered indices
    new_matrix = preds_matrix.copy()
    for i in range(1, preds_matrix.shape[0]):
        pred_indices = preds_matrix[i]
        _, ind_dict = get_matching_indices(ref_indices=ref, pred_indices=pred_indices)
        ordered = np.zeros((len(ind_dict.keys()), pred_indices.shape[0]))
        for m, (n, l) in enumerate(ind_dict.items()):
            ordered[m] = np.where(pred_indices==n, l, 0)
        ordered_label = np.sum(ordered, 0).astype(np.int64)
        ## Assign ordered indices
        new_matrix[i] = ordered_label

    return new_matrix

 

홍머스 정리

• linear_sum_assignment 함수 말고도 Munkres 라는 라이브러리로 수행할 수 있음.
• Hungarian 알고리즘은 Kuhn 알고리즘 혹은 Munkres 알고리즘이라고도 불림
• 매칭할 클래스가 많으면 매우 오래걸림. 시간복잡도는 $O(V^3)$ ($V$는 클래스 개수). 일일히 모든 경우를 다 찾는 brute-force 의 시간복잡도는 $O(V!)$

참조

• complex-systems-ai.com/automated-planning-and-scheduling/hungarian-method/
• brilliant.org/wiki/hungarian-matching/
• docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html