군집 결과 평가: 헝가리안 알고리즘 기반 레이블 매핑을 통한 정확도 계산

군집 알고리즘은 데이터를 그룹화하지만, 생성된 군집 레이블(예: 0, 1, 2)은 실제 클래스 레이블(예: '고양이', '개', '새')과 직접적으로 일치하지 않을 수 있습니다. 예를 들어, 군집 0이 실제로는 '개'에 해당하고, 군집 1이 '고양이'에 해당할 수 있습니다. 따라서 군집 분석의 정확도를 의미 있게 평가하기 위해서는 예측된 군집 레이블과 실제 레이블 간의 최적의 매핑을 찾아야 합니다. 이 과정에 헝가리안 알고리즘(Hungarian Algorithm)이 효과적으로 활용될 수 있습니다.

본 문서에서는 Python과 MATLAB을 사용하여 헝가리안 알고리즘을 통해 군집 레이블을 실제 레이블에 맞게 조정한 후, 정확도를 계산하는 방법을 다룹니다.

1. Python으로 군집 정확도 계산

Python에서는 scipy.optimize.linear_sum_assignment 함수를 사용하여 헝가리안 알고리즘을 구현할 수 있습니다. 다음 함수는 예측 레이블과 실제 레이블을 입력받아 최적의 매핑을 적용한 후 정확도를 반환합니다.

import numpy as np
from scipy.optimize import linear_sum_assignment

def calculate_adjusted_accuracy(true_labels, predicted_labels):
    """
    헝가리안 알고리즘을 사용하여 군집 레이블을 최적으로 매핑한 후 정확도를 계산합니다.

    Args:
        true_labels (numpy.ndarray): 실제 클래스 레이블 배열.
        predicted_labels (numpy.ndarray): 군집 알고리즘이 예측한 레이블 배열.

    Returns:
        float: 레이블 조정 후 계산된 정확도.
    """
    # 레이블이 정수형인지 확인합니다.
    true_labels = true_labels.astype(np.int64)
    predicted_labels = predicted_labels.astype(np.int64)

    # 레이블 배열의 크기가 일치하는지 검증합니다.
    if true_labels.size != predicted_labels.size:
        raise ValueError("실제 레이블과 예측 레이블의 크기가 일치해야 합니다.")

    # 전체 고유 클래스/군집의 개수를 결정합니다.
    # 이는 매핑 행렬의 차원을 설정하는 데 사용됩니다.
    num_unique_labels = max(true_labels.max(), predicted_labels.max()) + 1

    # 매핑 비용 행렬(또는 일치 행렬)을 생성합니다.
    # mapping_matrix[i, j]는 예측 레이블 'i'가 실제 레이블 'j'에 해당하는 샘플 수를 저장합니다.
    mapping_matrix = np.zeros((num_unique_labels, num_unique_labels), dtype=np.int64)
    for i in range(true_labels.size):
        mapping_matrix[predicted_labels[i], true_labels[i]] += 1

    # 헝가리안 알고리즘은 기본적으로 최소 비용 할당 문제를 해결합니다.
    # 우리는 정확도(일치하는 샘플 수)를 최대화해야 하므로,
    # 행렬의 각 요소를 행렬 내 최댓값에서 빼서 최대화 문제를 최소화 문제로 변환합니다.
    cost_for_minimization = mapping_matrix.max() - mapping_matrix

    # linear_sum_assignment 함수를 사용하여 최적의 할당을 찾습니다.
    # row_ind, col_ind는 각각 할당된 행과 열의 인덱스를 반환합니다.
    row_ind, col_ind = linear_sum_assignment(cost_for_minimization)

    # 최적의 매핑에 따라 정확하게 매핑된 샘플들의 합계를 계산합니다.
    correctly_mapped_samples = mapping_matrix[row_ind, col_ind].sum()

    # 정확도는 올바르게 매핑된 샘플 수를 전체 샘플 수로 나눈 값입니다.
    accuracy = correctly_mapped_samples / true_labels.size
    return accuracy

# 예제 데이터
실제_레이블_데이터 = np.array([2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1])
예측_레이블_군집_A = np.array([1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 2, 3, 1, 3, 3, 2, 3])
예측_레이블_군집_B = np.array([2, 2, 3, 2, 2, 3, 3, 3, 1, 3, 3, 1, 2, 1, 1, 3, 1])

# 헝가리안 알고리즘을 통한 정확도 계산
정확도_군집_A = calculate_adjusted_accuracy(실제_레이블_데이터, 예측_레이블_군집_A)
정확도_군집_B = calculate_adjusted_accuracy(실제_레이블_데이터, 예측_레이블_군집_B)

print(f"군집 A의 조정된 정확도: {정확도_군집_A}")
print(f"군집 B의 조정된 정확도: {정확도_군집_B}")

위 코드 실행 결과:

군집 A의 조정된 정확도: 0.6470588235294118
군집 B의 조정된 정확도: 0.6470588235294118

2. MATLAB으로 군집 정확도 계산

MATLAB에서는 헝가리안 알고리즘을 직접 구현하거나 외부 함수를 사용할 수 있습니다. 여기서는 munkres 함수를 사용하여 레이블을 매핑하고 정확도를 계산하는 과정을 보여줍니다.

2.1. MATLAB 메인 스크립트

아래 스크립트는 원시 예측 레이블을 헝가리안 알고리즘을 통해 실제 레이블에 맞게 조정한 후 정확도를 계산합니다. map_cluster_labels 및 munkres 함수가 필요합니다.

%% MATLAB 예제: 군집 정확도 계산
clear;
clc;

% 실제 레이블과 예측 레이블 데이터 정의
실제_레이블 = [2 2 2 2 2 2 3 3 3 3 3 3 1 1 1 1 1];
예측_레이블_원시 = [1 1 2 1 1 2 2 2 3 2 2 3 1 3 3 2 3];

% --------------------------------------------------
% 헝가리안 알고리즘을 사용하여 예측 레이블을 실제 레이블에 최적으로 매핑
% 이 과정은 군집 알고리즘의 출력 레이블이 실제 클래스 레이블과 직접 일치하지 않을 때 필요합니다.
조정된_예측_레이블 = map_cluster_labels(예측_레이블_원시, 실제_레이블);

% 레이블 조정 전의 원시 정확도 (참고용, 매핑되지 않은 상태)
% 주의: 이 '정확도'는 예측 레이블과 실제 레이블을 직접 비교한 것으로,
% 레이블 불일치 문제로 인해 의미 있는 군집 정확도를 나타내지 않을 수 있습니다.
원시_정확도 = sum(실제_레이블 == 예측_레이블_원시) / length(실제_레이블);
fprintf('레이블 조정 전 원시 정확도: %f\n', 원시_정확도);

% 헝가리안 알고리즘으로 레이블 조정 후의 정확도 계산
% 이 값은 군집 성능을 올바르게 평가한 정확도입니다.
조정_후_정확도 = sum(실제_레이블 == 조정된_예측_레이블) / length(실제_레이블);
fprintf('헝가리안 알고리즘으로 레이블 조정 후 정확도: %f\n', 조정_후_정확도);

% 또한, 'Evaluate' 함수 (주로 이진 분류 지표용)를 사용하여 다른 지표도 확인할 수 있습니다.
% 'Evaluate' 함수는 첫 번째 클래스(여기서는 1)를 기준으로 지표를 계산하므로,
% 전체 군집 정확도와는 다를 수 있습니다.
fprintf('\n--- 추가 성능 지표 (Evaluate 함수 사용) ---\n');
evaluation_results_unadjusted = Evaluate(실제_레이블, 예측_레이블_원시);
fprintf('원시 레이블 (클래스 1 기준) 정확도: %f\n', evaluation_results_unadjusted(1));

evaluation_results_adjusted = Evaluate(실제_레이블, 조정된_예측_레이블);
fprintf('조정된 레이블 (클래스 1 기준) 정확도: %f\n', evaluation_results_adjusted(1));

위 코드 실행 결과:

레이블 조정 전 원시 정확도: 0.294118
헝가리안 알고리즘으로 레이블 조정 후 정확도: 0.647059

--- 추가 성능 지표 (Evaluate 함수 사용) ---
원시 레이블 (클래스 1 기준) 정확도: 0.294118
조정된 레이블 (클래스 1 기준) 정확도: 0.647059

2.2. 보조 함수: munkres (헝가리안 알고리즘)

munkres 함수는 Munkres 할당 알고리즘을 구현하여 비용 행렬에 대한 최적의 할당을 찾아냅니다.

function [assignment,cost] = munkres(costMat)
% MUNKRES   Munkres 할당 알고리즘
% [ASSIGN,COST] = munkres(COSTMAT)은 COSTMAT으로 표현된 할당 문제에 대해
% 최소 비용을 가진 최적의 할당을 ASSIGN으로 반환합니다.
% (i,j)번째 요소는 j번째 작업을 i번째 작업자에게 할당하는 비용을 나타냅니다.
% 이 구현은 벡터화되어 있으며 Matlab에서 가장 빠른 구현 중 하나입니다.

assignment = false(size(costMat));
cost = 0;
 
costMat(costMat~=costMat)=Inf;
validMat = costMat<Inf;
validCol = any(validMat);
validRow = any(validMat,2);
 
nRows = sum(validRow);
nCols = sum(validCol);
n = max(nRows,nCols);
if ~n
    return
end
     
dMat = zeros(n);
dMat(1:nRows,1:nCols) = costMat(validRow,validCol);
 
%*************************************************
% Munkres 할당 알고리즘 시작
%*************************************************
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   STEP 1: 각 행에서 행의 최솟값을 뺍니다.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 dMat = bsxfun(@minus, dMat, min(dMat,[],2));
 
%************************************************************************** 
%   STEP 2: dMat의 0을 찾습니다. 해당 열이나 행에 별표(starred)된 0이 없으면 해당 0에 별표를 합니다.
%           각 0에 대해 반복합니다.
%**************************************************************************
zP = ~dMat;
starZ = false(n);
while any(zP(:))
    [r,c]=find(zP,1);
    starZ(r,c)=true;
    zP(r,:)=false;
    zP(:,c)=false;
end
 
while 1
%**************************************************************************
%   STEP 3: 별표된 0이 있는 각 열을 덮습니다. 모든 열이 덮이면 매칭이 최대입니다.
%**************************************************************************
    primeZ = false(n);
    coverColumn = any(starZ);
    if ~any(~coverColumn)
        break
    end
    coverRow = false(n,1);
    while 1
        %**************************************************************************
        %   STEP 4: 덮이지 않은 0을 찾아 프라임합니다. 이 프라임된 0을 포함하는 행에 별표된 0이 없으면 Step 5로 이동합니다.
        %           그렇지 않으면 이 행을 덮고 별표된 0을 포함하는 열을 덮지 않습니다.
        %           덮이지 않은 0이 없을 때까지 이 과정을 계속합니다.
        %           가장 작은 덮이지 않은 값을 저장하고 Step 6으로 이동합니다.
        %**************************************************************************
        zP(:) = false;
        zP(~coverRow,~coverColumn) = ~dMat(~coverRow,~coverColumn);
        Step = 6;
        while any(any(zP(~coverRow,~coverColumn)))
            [uZr,uZc] = find(zP,1);
            primeZ(uZr,uZc) = true;
            stz = starZ(uZr,:);
            if ~any(stz)
                Step = 5;
                break;
            end
            coverRow(uZr) = true;
            coverColumn(stz) = false;
            zP(uZr,:) = false;
            zP(~coverRow,stz) = ~dMat(~coverRow,stz);
        end
        if Step == 6
            % *************************************************************************
            % STEP 6: 덮이지 않은 최솟값을 각 덮인 행의 모든 요소에 더하고,
            %         각 덮이지 않은 열의 모든 요소에서 뺍니다.
            %         별표, 프라임, 덮인 선을 변경하지 않고 Step 4로 돌아갑니다.
            %**************************************************************************
            M=dMat(~coverRow,~coverColumn);
            minval=min(min(M));
            if minval==inf
                return
            end
            dMat(coverRow,coverColumn)=dMat(coverRow,coverColumn)+minval;
            dMat(~coverRow,~coverColumn)=M-minval;
        else
            break
        end
    end
    %**************************************************************************
    % STEP 5:
    %  프라임된 0과 별표된 0이 번갈아 나타나는 일련의 경로를 구성합니다.
    %  Z0을 Step 4에서 찾은 덮이지 않은 프라임된 0으로 둡니다.
    %  Z1을 Z0의 열에 있는 별표된 0으로 둡니다 (있다면).
    %  Z2를 Z1의 행에 있는 프라임된 0으로 둡니다 (항상 있을 것입니다).
    %  이 시리즈가 해당 열에 별표된 0이 없는 프라임된 0에서 끝날 때까지 계속합니다.
    %  시리즈의 각 별표된 0의 별표를 해제하고, 각 프라임된 0에 별표를 하며,
    %  모든 프라임을 지우고 행렬의 모든 선을 덮지 않습니다. Step 3으로 돌아갑니다.
    %**************************************************************************
    rowZ1 = starZ(:,uZc);
    starZ(uZr,uZc)=true;
    while any(rowZ1)
        starZ(rowZ1,uZc)=false;
        uZc = primeZ(rowZ1,:);
        uZr = rowZ1;
        rowZ1 = starZ(:,uZc);
        starZ(uZr,uZc)=true;
    end
end
 
% 할당 비용
assignment(validRow,validCol) = starZ(1:nRows,1:nCols);
cost = sum(costMat(assignment));
end

2.3. 보조 함수: map_cluster_labels (레이블 매핑)

map_cluster_labels 함수는 munkres 함수를 활용하여 예측된 군집 레이블을 실제 레이블에 최적으로 매핑합니다.

function [ mapped_labels ] = map_cluster_labels( predicted_labels, true_labels )
% 실제 레이블에 맞춰 예측 레이블을 최적으로 매핑합니다.
% 이 함수는 'munkres' (헝가리안 알고리즘) 함수를 필요로 합니다.

% 고유한 실제 레이블의 개수를 K로 설정합니다.
num_classes = length(unique(true_labels));

% 매핑 비용 행렬을 초기화합니다.
% cost_matrix(i, j)는 예측 레이블 'i'가 실제 레이블 'j'에 매핑될 때 발생하는 오분류 수를 나타냅니다.
cost_matrix = zeros(num_classes, num_classes);

% 비용 행렬을 채웁니다.
% 각 예측 클러스터 'i'에 대해, 해당 클러스터에 속하는 샘플들이 실제 레이블 'j'와 얼마나 다른지 계산합니다.
for i = 1:num_classes
    % 예측 레이블 'i'에 해당하는 모든 샘플 인덱스를 찾습니다.
    indices_in_pred_cluster = find(predicted_labels == i);
    
    for j = 1:num_classes       
        % 이 클러스터의 샘플 중 실제 레이블이 'j'가 아닌 것들의 수를 세어 비용으로 설정합니다.
        % 즉, 예측 'i'를 실제 'j'로 매핑했을 때의 오분류 비용입니다.
        cost_matrix(i, j) = length(find(true_labels(indices_in_pred_cluster) ~= j));
    end
end

% 헝가리안 알고리즘을 사용하여 최적의 매핑을 찾습니다.
% munkres 함수는 최소 비용 할당을 수행합니다.
[assignment_matrix, ~] = munkres(cost_matrix);

% 할당 행렬에서 최적의 매핑 순서를 추출합니다.
% assigned_mapping(i)는 예측 클러스터 'i'가 매핑되어야 할 실제 레이블입니다.
[~, assigned_mapping] = find(assignment_matrix');

% 새로운 매핑된 레이블 배열을 생성합니다.
mapped_labels = predicted_labels;

% 최적의 매핑 규칙에 따라 예측 레이블을 업데이트합니다.
for i = 1:num_classes
    % 예측 레이블 'i'를 가진 모든 샘플의 레이블을 매핑된 레이블로 변경합니다.
    indices_to_update = find(predicted_labels == i);
    mapped_labels(indices_to_update) = assigned_mapping(i);
end

end

2.4. 보조 함수: Evaluate (성능 지표 계산)

Evaluate 함수는 분류 모델의 일반적인 성능 지표(정확도, 민감도 등)를 계산합니다. 이 예제에서는 주로 정확도를 확인하는 데 사용됩니다.

function result = Evaluate(real_label,pre_label)
% 이 함수는 분류 모델의 성능을 평가하고 일반적인 성능 측정값을 계산합니다:
% Accuracy, Sensitivity, Specificity, Precision, Recall, F-Measure, G-mean.
% 입력: ACTUAL = 실제 클래스 레이블 열 벡터
%       PREDICTED = 분류 모델이 예측한 클래스 레이블 열 벡터
% 출력: EVAL = 모든 성능 측정값을 포함하는 행 벡터
% https://www.mathworks.com/matlabcentral/fileexchange/37758-performance-measures-for-classification
 
% 이 함수는 주로 이진 분류를 위해 설계되었으므로,
% real_label == 1 인덱스를 기준으로 지표를 계산합니다.
% 다중 클래스 정확도를 직접 계산하려면 다른 방식이 필요할 수 있습니다.
idx = (real_label()==1);
 
p = length(real_label(idx)); % 실제 양성(Positive) 샘플 수
n = length(real_label(~idx)); % 실제 음성(Negative) 샘플 수
N = p+n; % 전체 샘플 수
 
tp = sum(real_label(idx)==pre_label(idx)); % True Positive
tn = sum(real_label(~idx)==pre_label(~idx)); % True Negative
fp = n-tn; % False Positive
fn = p-tp; % False Negative
 
tp_rate = tp/p; % True Positive Rate (민감도)
tn_rate = tn/n; % True Negative Rate (특이성)
 
accuracy = (tp+tn)/N; % 정확도
sensitivity = tp_rate;  % 민감성 (True Positive Rate)
specificity = tn_rate; % 특이성 (True Negative Rate)
precision = tp/(tp+fp);  % 정밀도
recall = sensitivity;  % 재현율
f_measure = 2*((precision*recall)/(precision + recall));  % F-measure
gmean = sqrt(tp_rate*tn_rate); % G-mean
Jaccard=tp/(tp+fn+fp); % 자카드 계수
 
result = [accuracy sensitivity specificity precision recall f_measure gmean Jaccard];
end

태그: python Matlab clustering Accuracy Hungarian Algorithm

10월 29일 11:45에 게시됨