범주형 변수로 측정된 두 관측치 간 거리를 계산하는 가장 간단한 방법은 해밍거리이다. 그러나 해밍 거리는 범주형 변수들 사이의 관계를 지나치게 단순하게 계산하는 단점을 가지고 있다. 이에 범주형 변수로 구성된 두 관측치 사이의 거리를 측정하기 위한 다양한 방법들이 제안되었다(Gooall, 1966; Smirnov, 1968; Burnaby, 1970; Stanfill and Waltz, 1986; Lin, 1988; Cost and Salzberg, 1993; Cheng et al., 2004; Le and Ho, 2005; Xie, 2010). 두 범주형 관측치 사이의 거리를 측정하는 방법은 크게 부류(Class) 정보를 이용하는 지도 학습 방법(Supervised learning method)과 부류 정보를 이용하지 않는 비지도 학습 방법(Unsupervised learning method)으로 나뉜다.

Stanfill과 Waltz (1986)는 부류 정보를 잘 구분할 수 있는 범주형 변수 값에 높은 가중치를 주는 Value Difference Metric(VDM)를 제안하였다. 그러나 VDM은 두 변수 값의 차이가 대칭적이지 않은 문제점이 있어 Cost와 Salzberg (1993)는 이를 수정 보완한 Modified Value Difference Model (MVDM)을 제안하였다. VDM과 MVDM 모두 조건부 확률을 이용하여 두 변수 값의 차이 (즉, 거리)를 정의하였다. 이에 반해 Xie (2010)는 경사하강법을 이용해 범주형 변수 값에 실수(real number)를 대응시키는 방법을 제안하였다. Xie (2010)가 제안한 방법은 임의의 실수 값을 범주형 변수 값에 대응시킨 다음 k-최근접 이웃 분류 수행하고 이를 통해 예측한 부류 값과 실제 부류 정보와의 오차를 계산한 뒤 경사하강법을 통해 대응된 실수 값을 조금씩 수정하여 오차를 최소화하는 실수 값을 찾는 방법이다. 이와 유사하게 Cheng et al (2004)은 경사하강법을 이용한 Adaptive dissimilarity matrix를 제안하였다. 그들은 임의의 실수 값을 수정하는 Xie (2010) 방법과는 다르게 경사하강법을 통해 두 변수 값 사이의 비유사도를 직접 수정하는 방법이다. 그러나 언급한 모든 방법은 부류 정보가 있어야 적용이 가능한 지도 학습 방법이다.

앞서 논의한 지도 학습 방법과 달리 부류 정보를 이용하지 않는 비지도 학습 방법 또한 다양하게 제안되었다(Gooall, 1966; Smirnov, 1968; Burnaby, 1970; Lin, 1988; Le and Ho, 2005). Goodall(1966)은 두 변수 값 사이의 유사도(두 변수가 동일한 같은 경우 유사도가 가장 높음)를 계산 하는 방법으로 희소하게 발생하는(빈도가 낮은) 변수 값이 동일한 경우에 상대적으로 더 높은 유사도를 부여하는 방식을 제안했다. 그러나 Goodall(1966)이 제안한 방법은 두 변수 값이 불일치하는 경우를 0의 유사도를 가지도록 함으로 인해 상이한 두 변수 값의 차이 정도가 지나치게 단순화 된다는 단점이 있었다. 이를 극복하고자 Smirnov(1968)는 두 변수 값이 불일치하는 경우에 0이 아닌 값을 부여하는 방법을 제안하였다. 이 방식은 두 변수 값이 동일한 경우에는 그것이 희소한 변수 값일 경우에 상대적으로 더 높은 유사도를 부여하고 두 변수 값이 불일치하는 경우에는 불일치하는 두 변수 값을 제외한 나머지 변수값들을 고려한 유사도를 부여한다. 확률적 방법에 기반한 Goodall(1966)과 Smirnov(1968)의 방법은 두 변수 값이 일치하는 경우에 더 중점을 둔 방법이다. 그러나 Burnaby(1970)과 Lin (1988)은 정보이론(Information theory)에 기반을 두어 두 변수 값이 불일치하는 경우에 보다 초점을 둔 방법을 제안하였다. Burnaby(1970)는 두 변수 값이 일치하는 경우에는 간단하게 유사도 값을 1로 계산하고, 희소한 두 변수 값이 불일치하는 경우는 비유사도 값을 높게 부여함으로써 상대적으로 유사도 값이 낮아지는 방법을 제안했다. Lin (1988)은 Burnaby(1970)의 방법과는 다르게 자주 발생하는 두 변수 값이 일치하는 경우 1보다 큰 유사도 값을 부여하였으며, 희소하게 발생하는 두 변수값이 불일치하는 경우 더 큰 비유사도 값을 부여하는 방법을 제시하였다. 그러나 앞서 설명한 모든 비지도 학습 방식은 범주형 변수들 사이의 관계(즉, 연관성)를 고려하지 않는 단점을 가지고 있다. 이에 Le 와 Ho(2005)는 변수들 간의 연관성을 고려한 연관성 기반 비유사도(Association-based dissimilarity) 방법을 제안하였다. Le 와 Ho(2005)는 두 변수 값 사이의 비유사도를 다른 변수 값들의 조건부 확률 분포 간 차이로 계산하였으며 범주형 변수 사이에 연관성이 존재할 때 연관성을 고려하지 않는 방법들에 비해 더 우수한 성능이 나타남을 보였다.

다음은 본 연구에서 제안한 변수 선택 방법의 효과성을 살펴보기 위해 선택한 두 범주형 관측치 간의 거리를 계산하는 방법에 관해 서술하고자 한다. 본 연구에서 관측된 n개의 관측치로 이루어진 데이터 셋을 X = {X₁, X₂, ..., X_n}으로 표기하며, 각 관측치는 p차원의 범주형 확률 변수로 측정되었다. 임의의 한 범주형 확률 변수 A_i는 r_i개의 범주형 변수 값을 가지며 A_i = {a_i1, a_i2,..., a_iri}로 표현된다. 범주형 확률 변수에서는 수치형 확률 변수와 달리 임의의 두 변수 값 사이의 차이가 정의되어 있지 않으므로 두 관측치 사이의 거리를 계산하기 전에 먼저 두 범주형 변수 값 사이의 차이인 비유사도를 정의하였다. 임의의 한 범주형 확률 변수(A_i)의 두 변수값 a_ij와 a_ik 사이의 비유사도는 d(a_ij, a_ik)로 표현했으며. 두 관측치 x_g와 x_h 간 거리는 d(x_g, x_h)로 표현한다.

변수 선택은 p 개의 변수를 가지는 변수 집합 F에서 중요한 변수 일부만을 선택하여 부분 집합 S를 구성하는 작업이다(Oh, 2008). 변수 선택의 핵심 조건은 원본 데이터 변수의 수를 감소시킴에도 불구하고 원본 데이터의 중요한 정보를 잃지 않는 것이다. 변수 선택을 통해 얻는 가장 큰 이점은 계산 시간의 감소와 함께 차원의 저주를 피함으로써 일반화 능력을 갖추는 것이다. 변수선택 방법은 부분 집합을 생성하고(부분 집합 생성기) 생성된 부분 집합을 평가하는(분별력 측정기) 두 가지 함수로 구성된다. 변수선택 방법은 계산 시간을 고려하지 않는다면 가능한 모든 부분 집합을 생성하고 가장 우수한 평가를 받은 부분 집합을 선택하는 단순한 문제이지만, 변수의 개수가 늘어남에 따라 계산 시간이 기하급수적으로 증가한다. 따라서 이를 개선하기 위한 많은 변수 선택 기법들이 제안되었다.

변수 선택 기법은 작동 원리에 따라 크게 임베디드 (Embedded), 래퍼(Wrapper), 필터(Filter) 방법으로 분류 된다(Guyon et al., 2003). 임베디드 방법은 부분 집합의 생성 및 선택 과정이 모형학습 과정에 포함이 되어있다. 대표적인 방법으로 C4.5(Quinlan, 2014)나 LASSO(Tibshirani, 1996)가 이에 해당한다. 래퍼 방법은 특정 모형의 성능 향상에 가장 이상적인 변수의 조합 찾는 방법이다. 회귀분석의 전진 선택법 (Forward selection), 후진 제거법(Backward elimination), 단계 선택법 (step-wise selection)이 래퍼 방법에 해당한다. 래퍼 방법은 다른 방법에 비해 정확도가 높은 장점이 있으나 과적합 문제와 계산 비용이 많이 든다는 단점이 있다(Liu et al., 2009). 마지막으로 필터 방법은 모형학습과 독립적으로 변수 집합 F에서 적합도 평가지표 (goodness measure)를 이용하여 기준 조건을 충족하는 변수를 선택함으로써 부분 집합을 구성하는 방법이다. 평가지표로는 주로 상관 계수(Correlation coefficient)을 사용하거나 정보이론의 엔트로피(Entropy)를 이용한다. 필터 방법은 래퍼 방법과 비교하여 성능이 다소 낮으나 계산 시간이 작으며 과적합(Overfitting)을 피할 수 있다는 장점이 있다.

변수 선택 기법을 분류하는 또 다른 기준으로는 부류 정보(Class information)의 이용 여부이다. 부류 정보를 이용하는 기법인 지도 변수 선택(Supervised feature selection)과 부류 정보를 이용하지 않는 기법인 비지도 변수 선택(Unsupervised feature selection)으로 나뉜다(Luis 2000; Part Punpiti 2014; Park and Kim 2014). C4.5, Lasso, 단계 선택법 등의 방법들은 모두 부류 정보를 이용하는 지도 변수 선택 방법이다. 지도 변수 선택은 비지도 선택 방법에 비해 상대적으로 다양한 방법들이 논의되었으나(Yu and Liu 2003, Liu et al., 2009; Vergara and Estevez 2013). 이에 반해 비지도 변수 선택 방법은 상대적으로 적은 관심을 받아 왔다(Luis 2000; Part Punpiti 2014). 비지도 변수선택 방법은 일반적으로 지도 선택 방법에 비해 과적합(Overfiting) 경향이 작은 장점을 가지고 있다(Guyon et al., 2003). 그러나 많은 수의 비지도 변수 선택 방법은 범주형 자료에 적용이 불가능 하다. 이에 본 연구에서는 부류 정보가 없는 고차원 범주형 자료에 적용 가능한 연관성 기반 변수 선택 방법을 제안하고자 한다.

적합도 평가 지표를 정의하기 위해서는 적합 변수에 대한 사전 정의가 필요하다. 대부분의 지도 변수 선택 기법들은 부류 정보와 연관성이 높은 변수를 적합 변수(Relevance variables)로 정의한다(Blum and Langley, 1997). 그러나 본 연구에서는 부류 정보가 없는 상황이므로 이와 같은 방법으로 적합 변수를 정의할 수 없다. Luis (2009)는 군집 분석을 위한 변수 선택 기법을 제시하였는데 그의 연구에서는 변수들 간 연관성이 높은 변수를 적합 변수로, 변수들 간 연관성이 낮은 변수들은 불필요한 변수로 정의하였다. 본 연구에서는 Luis (2009)의 적합 변수 정의 방식에 따라 적합 변수와 부적합 변수를 정의한다.

변수와의 연관성을 정의하는 일반적인 방법은 피어슨 상관 계수(Pearson correlation coefficient)이다. 그러나 피어슨 상관 계수는 비선형적 관계를 반영하지 못하며, 범주형 변수에는 적용할 수 없다. 이런 단점을 극복하기 위해 정보이론의 엔트로피 개념을 기반으로 한 변수 간 연관성 측정 방법이 제시되었다(Yu and Liu, 2003). 따라서 본 연구에서는 변수 간 연관성을 엔트로피 개념을 사용하여 정의한다.

엔트로피는 확률 변수 A_i가 가질 수 있는 모든 사건에 대한 정보량을 평균한 값이다. 엔트로피 값이 크다는 것은 사건의 불확실성이 크다는 것을 의미하고 통계적으로는 모든 사건이 동일한 확률을 가지는 것을 의미한다. 확률 변수 A_i의 엔트로피는 아래의 수식 (5)를 통해 계산한다(Vergara and Estévez, 2014).

다음으로 임의의 두 범주형 확률 변수 A_i와 Ai'에 대한 조건부 엔트로피는 아래의 수식 (6)을 통해 계산된다(Vergara and Estévez, 2014).

여기서 ∀i, i'∈{1, 2, ..., p^}, ∀j∈{1, 2, ...,ri}, ∀s∈{1, 2, ..., ri'}이며 p(ai's|aij)는 조건부 확률이다. 만약 두 범주형 확률 변수 A_i와 Ai'가 완전히 종속이면 H(Ai'|Ai)는 0되고 독립이면 H(Ai'|Ai)는 H(Ai')이 된다. 따라서 조건부 엔트로피는 아래의 수식 (7)의 관계식을 만족한다(Vergara and Estévez, 2014).

조건부 엔트로피 H(Ai'|Ai)를 정규화하기 위해 이를 상한 값 H(Ai')으로 나눈 값을 D(Ai'|Ai)로 표기하면 아래의 수식 (8)와 같다.

여기서 D(Ai',Ai)는 H(Ai'|Ai)/H(A_i)이며, D(Ai',Ai) 값이 0이면 Ai'는 A_i에 종속, 1이면 독립이다.

본 장에서는 앞서 정의한 정규화된 조건부 엔트로피 D(Ai',Ai)를 통한 평가 기준을 정의하고 이를 이용하여 적합 변수를 선정하고자 한다. 임의의 범주형 확률 변수 A_i가 다른 변수들에 대해 가지는 의존도는 아래의 수식 (9)와 같이 정의된 개별 독립성 점수(Individual independence score)로 측정 할 수 있다.

여기서 ID(A_i)은 범주형 확률 변수 A_i와 다른 범주형 확률 변수 Ai'들의 정규화 된 조건부 엔트로피의 평균값이다. 독립성 점수 ID(A_i)가 1이면 다른 모든 변수들과 독립이고, 0이면 모든 변수들과 종속이다. 정의된 독립성 점수 ID(A_i)와 적합도 평가 지표 D(Ai',Ai)와의 관계를 통하여 적합 변수 선정 여부를 결정하는 평가 기준과 이를 이용한 개별 적합 변수 집합(Individual relevant variables set)을 아래의 수식 (10)와 같이 정의하였다.

여기서 F¬A_i는 확률 변수 A_i를 제외된 변수 집합을 의미하며 θ는 데이터의 특성을 조정 해주는 값을 의미한다. 수식 (10)이 의미하는 바는 A_i가 다른 전체 변수와 가지는 평균적인 연관성 ID(A_i)와 임의의 한 확률 변수 Ai'가 A_i와 가지는 연관성 D(Ai',Ai)를 상대적으로 비교하는 것이다. 예를 들어 대부분의 범주형 변수가 A_i와 독립이고 소수의 변수(A_i와 Ai')만이 종속인 경우, ID(A_i)는 1에 가까운 수를 가지지만 D(Ai',Ai)는 0에 가까운 수를 가진다. 따라서 ID(A_i)와 D(Ai',Ai)의 값을 비교를 통해 A_i에 대해 A_i′가 적합한 변수 인지 여부를 판정한다. 그러나 ID(A_i)는 범주형 확률 변수 A_i와 다른 범주형 변수들의 정규화 된 조건부 엔트로피의 평균값이기 때문에 ID(A_i)를 보정 없이 D(Ai',Ai)와 비교할 경우 평균적인 수의 범주형 변수가 δ(A_i)에 속하게 되는 문제점을 가지고 있다. 이를 해결하고자 본 연구에서는 전체 범주형 자료의 독립 점수 (Categorical data independence score)인 θ를 통해 개별 독립성 점수를 보정한 θ⋅ID(A_i)를 개별 적합 변수의 평가 기준으로 정의하였다. θ는 아래의 수식 (11)을 통해 계산된다.

θ는 전체 변수 쌍의 조합 가운데 독립적인 변수 쌍의 비율을 의미하며 전체 범주형 자료를 구성하는 범주형 변수의 독립정도를 의미한다. 여기서 θ가 0이면 모든 범주형 변수들은 서로 종속이며, 1이면 모든 범주형 변수들은 서로 독립이다. 범주형 변수의 사이의 독립성을 확인하는 방법으로 본 연구에서는 유의수준 0.01에서 χ² 검정을 시행하였다.

수식 (10)을 통해 계산된 개별 적합 변수 집합 δ(A_i)를 이용하여 적합 변수 집합(Relevance variables set, F_R)은 아래의 수식 (12)과 같이 정의할 수 있다.

이번 장에서는 앞서 정의된 적합변수 집합 FR={A1, ..., Ap'}에서 잉여변수(Redundancy variables)를 제거하는 방법에 대해 다룬다. 잉여변수는 적합 변수들 사이의 연관성을 통해 정의된다(Yu and Liu, 2003). 본 연구에서는 다른 적합 변수들 사이에 의존관계가 적은 변수를 잉여 변수로 보고 이를 제거하여 최적의 집합 S={A1, A2, ..., Ap^}을 찾는 방법을 제안한다. 앞서 수식 (10)를 통해 계산된 δ(A_i)는 기준 조건(D(Ai',Ai) ≤ θ⋅ID(A_i))을 만족하는 개별 적합 변수 집합을 의미한다. 따라서 집합의 크기(Cardinality)를 이용하면 임의의 범주형 변수 A_i와 의존 관계를 가지고 있는 변수의 수를 계산할 수 있다. card(δ(A_i))는 임의의 범주형 변수 A_i와 의존관계를 가지고 있는 변수의 수를 의미한다. 예를 들어 card(δ(A_i)) = 3이 의미하는 바는 임의의 변수 A_i와 의존 관계를 가지고 있는 범주형 변수가 총 3개임을 의미한다. δ(A_i) 집합의 크기와 적합 변수 집합의 크기 card(F_R)를 이용하면 임의의 변수 A_i가 다른 적합변수와 의존 관계를 맺고 있는 비율(Dependency ratio, μA_i))를 아래의 수식 (13)를 통해 계산 할 수 있다.

수식 (13)를 이용한 최적의 부분 집합 S는 아래의 수식 (14)과 같이 정의할 수 있다.

수식 (14)은 적합 변수 집합 F_R에 속한 범주형 변수들 중 임계치 상수 T 이상의 다른 변수들과 의존 관계를 맺고 있는 변수만을 선택하는 것을 의미한다. 임계치 상수 T는 0부터 1사이의 값으로 임계치 상수 T가 1이면 적합 변수 집합 F_R에 속한 모든 범주형 변수들과 의존 관계를 맺고 있는 범주형 변수만을 최적 부분 집합 S에 속하는 변수로 선택함을 의미하고 임계치 상수 T가 0이면 적합 변수 집합 F_R에 속한 모든 범주형 변수들이 최적 부분 집합 S의 변수로 선택됨을 의미한다. 본 연구에서는 임계치 상수 T를 중앙값인 0.5로 하였으며, 이는 적합 변수 집합F_R에 속한 범주형 변수 가운데 다른 범주형 변수들과 절반 이상의 의존 관계를 맺고 있는 변수만을 선택함을 의미한다. 아래의 Figure 1은 본 연구에서 제안한 변수선택 방법을 도식화한 것이다.

본 장에서는 시뮬레이션을 통해 임의로 고차원 범주형 자료를 생성하고 3-최근접 이웃 분류를 통해 기존의 방법 거리 측정 방법과 제안된 변수 선택을 적용한 거리 측정 방법의 성능을 비교하여 제안된 방법의 효과성을 살펴보고자 한다. 본 연구에서 제안한 방법의 효과성을 알아보기 위해 사용한 두 가지의 거리 방법은 해밍 거리(Hamming distance, HD)와 연관성 기반 비유사도(Association based dissimilarity, ABD)이다. 본 연구에서 제안한 변수선택 방법을 적용한 해밍거리를 HHD(High-dimensional Hamming distance)로 표기하고, 변수선택 방법을 적용한 연관성 기반 비유사도를 HABD(High-dimensional Association-based dissimilarity)로 표기하였다. 고차원의 범주형 데이터를 생성하기 위해 UCI repository로부터 실제 범주형 변수로 구성된 자료(Breast cancer)와 임의로 생성한 범주형 자료를 결합하였다. 실제 데이터인 Breast cancer 자료는 총 683개의 관측치와 9개의 범주형 변수로 구성되어 있으며 부류 정보는 2가지 값을 가진다. 임의로 생성한 범주형 변수는 범주형 변수의 수, 범주형 변수 값, 범주형 변수 값의 균형/불균형에 따라 총 6개의 사례를 제시하였다. 인위적으로 생성한 범주형 변수는 50개부터 50씩 증가시켜 600개의 변수를 생성하였고, 한 변수가 가질 수 있는 변수 값은 2부터 4까지 사례에 따라 다양하게 구성했다. 또한 각 변수의 변수 값의 빈도는 균형 혹은 불균형 상태로 다르게 생성하여 다양한 상황에 따른 제안 변수 선택방법의 효과를 살펴보고자 하였다. 아래의 Table 3는 실제 데이터와 인위적으로 생성한 데이터의 특징을 정리한 것이다.

본 장에서는 실제 데이터 (Breast cancer)와 각 시뮬레이션 사례를 결합하여 범주형 변수의 수를 증가시킴에 따라 변수 선택 여부에 따른 성능의 차이를 k-최근접 이웃 분류의 정확도를 통해 살펴보았다. 아래의 Table 4와 Figure 2는 각 사례 별로 k-최근접 이웃 분류의 정확도를 계산하고 도식화 한 것이다. 시뮬레이션 결과 모든 사례에서 변수선택 과정이 생략된 기존의 거리 측정 방법은 (HD와 ABD) 상호 독립적인 (즉, 연관성이 작은) 범주형 변수의 수가 늘어남에 따라 분류 정확도가 하락하는 것을 확인할 수 있었다. 즉 분석에 불필요한 변수의 수가 늘어감에 따라 유의미한 변수들을 선택하는 단계가 필요함을 의미한다. 또한, ABD의 경우 변수 값의 분포가 불균형한 경우(Case 4, Case 5, Case 6)에서 변수의 수가 늘어감에 따라 정확도가 더욱 심하게 하락하였다. 이에 반해 범주형 변수 값의 수에 따른 정확도의 차이는 크게 나타나지 않는 것으로 보인다. 다음으로 HHD와 HABD는 범주형 변수의 증가하더라도 동일한 정확도를 나타냈다. 이는 불필요한 변수의 수가 증가하더라도 본 연구에서 제안한 변수 선택 단계에서 분류 분석에 유의미한 변수만을 선택함을 의미한다. 아래의 Table 4는 각 사례에서 계산 된 최대, 최소, 평균 정확도와 그 표준편차를 의미한다.