Journal Archive

군집화를 포함한 많은 데이터 분석에 비유사성 측정이 사용된다[1][2]. 흔히 비유사성(Dissimilarity), 유사성, 거리, 근접성(Proximity) 등을 구분하지 않고 사용하지만 각각은 다소 다른 의미를 갖는다. 거리는 떨어진 정도를 나타내므로 유사성을 직접 나타내지 않는다. 유사성 s는 거리 r의 역수를 이용해서 s = 1/(1 + r) 형태로 사용한다[1][3]. 근접성은 가깝다는 의미를 내포하므로 유사성을 나타내는 다른 말이나 비유사성/유사성을 포괄하는 의미로 종종 사용한다. 비유사성은 대상의 다른 정도를 나타내므로 거리에 의해 직접 측정할 수 있는 것이다.

데이터를 분석하는 행위는 결국 패턴 찾기다. 모든 것이 같다면 아무 할 일이 없다. 데이터 분석의 많은 응용은 각자가 가진 고유한 방법에도 불구하고 거리 즉 비유사성을 측정을 전제로 한다. 덩어리를 찾아내는 군집화, 어디에 속하는지를 찾는 분류는 물론이고 요즘 많이 연구되는 추천시스템 들은 우선 거리를 측정하는 것에서 시작한다. 그런데 거리를 측정하는 것이 항상 가능한 것은 아니다. 예를 들어 두 사람의 취향이 비슷한지를 알려면 거리를 재야하는데, 취향을 잰다는 것이 쉽지는 않다.

본 논문은 비유사성을 측정할 수 있는 거리 연산에 관한 것이다. 먼저 데이터 과학의 제 분야에서 일반적으로 사용하는 거리 연산에 대해 알아보고, 떨어진 정도를 나타내는 거리 척도를 위한 수학적 정의와 조건이 완화된 거리에 대해 소개한다. 다음으로 주어진 데이터에서 준거리 관계를 생성하는 행렬연산 min_sum을 제안하고 증명한다. 이를 데이터 군집화에 적용하여 비유사성 측정 수단으로서 효과를 정성적으로 평가한다. 제안한 준거리 연산을 사용하는 경우 국가 사이의 교역량, 사람들 사이에 주고받은 문자 횟수 등 일반적으로 거리를 정의하기 어려운 데이터에 거리 개념을 부여하여 분류 및 군집화 등을 수행할 수 있다.

이 장에서는 거리에 대한 일반적인 정의와 비유사성 측정을 위해 흔히 사용하는 거리함수에 대해 설명한다. 다음으로 새로운 행렬연산 min-sum을 제안하고 이것이 준거리 조건을 만족하는 거리행렬을 생성함을 증명한다.

비유사성/유사성에 대해서는 주로 통계학의 분야에서 70년대까지 잘 정리되었다. 이어진 연구들은 특정 문제와 관련해서, 데이터 유형 즉, 수치데이터, 이진데이터, 범주형데이터, 혼합형데이터 등을 대상으로 비유사성 척도들을 어떻게 활용하는지 등에 관한 것이다[8][9]. 비유사성 척도를 정량적으로 비교하기는 어렵다. 비유적으로 사람을 비교하는데 키와 몸무게 중 어떤 것이 유용한지는 어디에 사용하느냐에 달린 문제다. 여기서는 ⊕연산이 상대적인 거리를 효과적으로 측정한다는 것을 정성적인 방법으로 보인다. 앞의 사례를 잘 살펴보면 직관적으로 a₃는 a₄ , a₂보다 a₁과 가깝다고 생각되지만 이를 정량적으로 판단하려면 거리를 구할 수 있어야 한다. 하지만 앞에서 본 것과 같이 주어진 데이터 항목의 거리관계를 나타낼 마땅한 방법이 없다. 대신 제안한 ⊕연산을 사용하여 준거리를 생성할 수 있음을 알았다.

그림 1은 이렇게 구한 행렬 F⊕F의 거리 관계를 MDS(Multi-Dimentional Scaling)을 이용해서 나타낸 것이다. MDS는 비유사성 즉, 거리가 정해진 데이터를 시각적으로 나타내는 일종의 그래프 레이아웃이다[3]. 넓은 의미에서는 높은 차원 데이터의 차원을 낮추는 것인데, 여기서는 평면에 나타내는 것이므로 2차원으로 낮춘다. 즉, 거리행렬을 입력으로 받아서 데이터 들 사이의 거리를 가장 잘 반영하는 좌표를 생성해준다. R 프로그래밍에서 제공하는 cmdscale() 함수를 사용하여 거리관계를 시각적으로 나타냈다. 그림은 a₃와 a₁이 상대적으로 가깝다는 것을 보여준다.

Fig. 1. 
Visualization distance relation in F⊕F

이상으로 ⊕연산으로 준거리를 생성하고 그것을 시각적으로 나타내 보았다. 이제 더 복잡한 데이터 집합의 군집화에 제안한 연산을 적용해 본다. 사용한 데이터는 미국 상원의 기명 투표 데이터다(http://www.voteview.com). 미국 상원 의원은 공화당, 민주당, 무소속으로 구성된다. 여기서는 투표 데이터를 군집화 하여 투표성향과 소속정당의 관계를 알아보려고 한다. 즉, 의원들의 법안에 대한 투표 데이터를 이용하여 의원들 사이의 거리를 구한 후 소속정당과 함께 시각적으로 나타내었을 때 군집이 형성되는지 알아보려 한다.

원 데이터의 편집과 클러스터링 과정은 참고문헌[3] 9장의 절차를 참고하였다. 표 2는 의원-투표 데이터 행렬을 나타낸다. 109번 회기를 기준으로 이 행렬의 크기는 101×644이다. 즉, 의원 101명이 644건의 법안에 투표한 결과다. 여기서 1은 찬성, 2는 반대, 3은 기권을 나타낸다. 어떤 두 의원의 벡터열이 일치할수록 두 의원의 투표성향이 같다고 할 수 있다. 따라서 일치하는 정도를 거리로 나타내면 투표성향이 같은 의원은 가까이 위치할 것이다. 이 때 각 의원의 위치를 소속정당으로 표시하면 투표 성향이 같은 사람들이 어떻게 분포하는지를 알 수 있다.

[3]에서는 의원들 사이의 거리를 의원-투표 행렬의 행 벡터별 유클리드 거리를 계산하여 측정하였다. 그림 2는 R 프로그램 결과를 나타낸다.

Fig. 2. 
Distance of senators(Euclid)

예를 들어 2번 의원(첫 번째)과 3번 의원 사이의 거리가 약 10임을 나타낸다. 또한 거리행렬은 대칭이므로 하삼각행렬로 표시되었음을 알 수 있다.

이제 이렇게 계산한 의원들 사이의 거리를 2차원 평면에 펼쳐놓으면 그들의 소속정당별 분포를 알 수 있다. 그러기 위해서 MDS를 적용하여 각 의원들의 좌표를 구한 결과는 표 3과 같다. 예를 들어 SHELBY의원은 민주당 소속이고 상대적 거리를 고려했을 때 위치좌표는 대략 (7.5, 0.95)임을 나타낸다.

이 결과를 시각화 하면 그림 3과 같다. 왼쪽에 민주당, 오른쪽에 공화당 의원이 군집을 형성함을 알 수 있다.

Fig. 3. 
Cluster(Euclid)

제안한 min-sum 연산을 적용하려면 먼저 의원들 사이의(잠재적) 거리를 나타내는 의원-의원 행렬을 구해야 한다. x-y 관계를 나타내는 데이터 행렬 M 이 주어지면 M*M^T와 M^T *M은 각각 x-x및 y-y관계를 나타내는 행렬이 된다(여기서 *는 행렬의 곱, M^T는 전치행렬). 따라서 의원-투표 행렬로부터 의원-의원 행렬을 구할 수 있다. 물론 이 행렬은 정의1의 거리조건을 만족하지 않으므로 거리 척도로 사용할 수 없다. 기존의 연구에서는 이렇게 얻은 의원-의원 행렬에 대해 행 벡터별 유클리드 거리를 계산하여 거리 행렬을 만드는 번거로운 과정을 거친다[3][7].

이제 의원들 사이의 준거리를 만들어 보자. 의원-투표 행렬을 M이라 하면, 의원-의원 행렬 N=M*M^T을 얻을 수 있다. 행렬 N의 대각성분을 0으로 수정한 행렬을 N(0)라 하면 정리2에의해 준거리 Q = [N(0)⊕N(0)]^m를 얻을 수 있다. 실제로 이 경우 m = 1이다. 그림 4, 표 4, 그림 5는 이렇게 구한 준거리 행렬 Q를 같은 방법으로 MDS로 시각화한 것이다.

Fig. 4. 
Distance of senators(min_sum)

Fig. 5. 
Cluster(min_sum)

그림 3과 마찬가지로 의원들의 투표성향이 소속 정당별로 군집을 형성함을 알 수 있다. 즉, 제안한 연산으로 생성한 준거리가 데이터의 특정속성을 분석하기에 적절함을 알 수 있다.

분류, 군집화, 추천 같은 데이터 분석의 다양한 분야가 데이터 항목의 비유사성 즉, 거리 측정을 필요로 한다. 데이터 집합의 거리관계는 항목들의 거리를 나타내는 거리행렬로 나타낼 수 있다. 데이터 집합이 항목-값 행렬로 주어지는 경우, 보통 항목벡터들의 유클리드 거리, 상관계수, 코사인 유사도 등을 이용하여 거리행렬을 구하는데, 이는 계산량이 많기도 하고, 직관적이지도 않다. 이 논문에서는 데이터 집합으로부터 직관적으로 만든 잠재적 거리행렬을 준거리 조건을 만족하는 행렬로 변환하는 행렬연산 min_sum을 제안하고, 이 연산을 반복 적용하면 준거리 행렬로 수렴함을 증명하였다. 제안한 연산을 군집화에 적용한 결과 종전의 방법과 같이 거리 척도로서 효과적임을 확인하였다.

이 논문에서는 제안한 행렬연산 min_sum이 거리 조건을 만족하지 않는 행렬을 준거리 조건을 만족하는 행렬로 변환함을 증명하고, 그렇게 얻어진 거리행렬이 비유사성을 효과적으로 측정함을 실제 문제에 적용하여 정성적으로 확인하였다. 다음으로 동일한 데이터에 대해 통상의 방법으로 생성한 거리행렬과 제안한 연산을 적용하여 생성한 준거리 행렬을 데이터 유형별로 분석하는 연구와 계산 복잡도를 비교하는 연구가 수행될 수 있겠다.