군집 알고리즘은 데이터를 그룹화하지만, 생성된 군집 레이블(예: 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