단백질은 대부분의 생명현상과 관련되어 있어서, 그 구조와 기능에 대한 연구가 활발하다. 단백질이 존재하는 세포내 위치 예측은 알려지지 않은 단백질의 기능에 대한 힌트를 얻기 위해 수행한다[1-9]. 이는 동물, 식물, 곰팡이와 같은 진핵생물은 세포 내부의 정교한 구획과 세포소기관이 존재하는데, 이러한 세포내 위치마다 서로 다른 생화학적 환경이 생기고, 이러한 환경에서 단백질은 위치 특이적인 기능을 수행하기 때문이다[10].

단백질의 세포내 위치 예측은 주로 하나의 단백질이 하나의 세포내 위치에만 나타나는 것을 대상으로 하였으나, 다중레이블 분류 기술의 발전에 따라서 다중위치에 대한 예측으로 확장되고 있다[1-9]. 다중레이블 분류는 하나의 입력 자료가 여러 분류에 속하는 문제를 처리하기 위해 연구되고 있다[11-13]. 다중레이블 분류가 단백질의 세포내 다중위치 예측에 적용된 예를 살펴보면, 최근접-이웃 분류기의 앙상블을 사용하는 방법[1, 7], 세포내 위치의 모든 쌍들에 대한 분류를 수행하고, 분류결과를 투표를 통하여 최종 결과를 얻는 방법[2], 가우시안 과정 모델과 공분산 행렬로 레이블간의 연관성을 표현하는 방법[3], 각 단일레이블에 관련된 사례들과 관련되지 않은 모든 사례들로 학습하고 분류를 위해서 투표를 하는 방법[4, 6], 다수의 이진 분류기를 체인으로 연결하고, k-번째 분류기는 이전 k−1개의 분류 예측결과를 이용하는 분류체인 방법을 앙상블로 사용하는 방법[5], 각 사례의 다중레이블 자체를 새로운 하나의 레이블로 만드는 레이블 멱집합방법을 변형하여 레이블 부분집합을 무작위로 만들고, 사례와 관련된 레이블을 사례의 속성으로 사용하는 방법[8] 등이 있다.

단백질의 세포내 위치예측 분야에서는 여러 다중레이블 분류 중에서 특정 생물학적 기능을 수행하는 단백질의 세포내 위치간의 관계를 효과적으로 모델링할 수 있는 분류체인 방법[14]과 레이블 멱집합 방법[15]이 성능이 높았다[5, 8, 9]. 본 논문에서는 레이블 멱집합 방법으로 기본 분류기를 구성하고, 각 다중레이블들이 예측될 확률을 구한다. 다중레이블에 속한 각 레이블별로 예측될 확률을 더하여 정해진 문턱치보다 크면 예측결과로 판정한다. 각 다중레이블들이 예측될 확률을 정교하게 구하기 위하여 쌍별 비교를 통한 확률추정 [16-18]과 오류정정 출력코드[19-21]에 대한 확률추정 [22]을 비교하였다. 본 논문에서는 각 다중레이블이 예측되는 확률을 가중치로 사용하여 단일레이블들의 예측 확률을 계산한다. 이렇게 계산된 단일레이블의 예측 확률이 정해진 문턱치보다 크면 예측된 레이블로 판정한다. 따라서 높은 확률로 예측되는 다중레이블들에 여러 차례 속하는 단일레이블의 예측확률은 강화되며, 학습 자료에 나타나지 않은 형태의 다중레이블을 예측할 수 있다.

본 논문의 내용과 관련이 깊은 레이블 멱집합 분류, 쌍별 비교와 오류정정 출력코드를 사용한 다중클래스 확률추정에 대해 알아본다.

다중레이블 분류 방법은 각 사례와 관련된 여러 개의 레이블들을 동시에 예측하므로, 하나의 레이블만을 예측하는 단일레이블 분류에 비하여 분류의 정확도가 높지 않다. 본 논문에서 사용하는 다중레이블 분류 방법인 레이블 멱집합 방법[11-13, 15]은 학습 자료에 나타나는 다중레이블들을 새로운 단일 레이블로 정의하여 다중레이블 분류를 단일 레이블 분류로 변환하는 방법이다. 이 방법은 직접적으로 레이블간의 연관관계를 나타낼 수 있는 장점이 있지만, 새로 정의된 단일레이블의 수가 많으면 분류기의 성능이 저하되고, 충분한 학습 자료가 없는 레이블에 해당하는 모델은 학습이 어렵다. 이를 해결하기 위해 PS(pruned sets) 방법[15]은 많은 사례를 가지는 다중레이블만을 사용하고, 학습에서 제외된 사례들의 다중레이블은 학습 자료로 선택된 다중레이블을 포함하는 경우에 학습 자료에 재도입된다.

EPS(ensemble of PS)[15]는 학습 자료의 일부(63%)를 표본 추출하여 학습되어진 PS 분류기를 사용한다. 이러한 과정을 여러 번 수행하여 예측된 다중레이블들에 포함된 단일레이블들의 개수를 구하고, 이 개수가 문턱치보다 크면 예측된 것으로 판정한다. 이러한 앙상블 방법은 분류기를 구성하는데 사용된 학습 자료에 과도적합(over-fitting)되는 것을 완화시키며, 학습 자료에 포함되지 않는 새로운 형태의 레이블 부분집합을 예측 할 수 있다.

다중클래스에 대한 확률추정을 위하여 쌍별 비교(pair-wise comparison)를 사용할 수 있다. 쌍별 비교는 단일레이블 분류에서 k개의 클래스(레이블과 같은 의미)를 가진 다중클래스 분류문제에 대하여 k(k−1)/2개의 모든 가능한 클래스 쌍에 대하여 이진클래스 분류를 수행하고, 이 분류 결과를 사용하여 다중클래스 분류를 하는 방법이다. 즉, 자료를 x, 이것의 클래스를 y라 할 때, 클래스 i와 j간의 이진클래스 분류를 통하여 쌍별 클래스 확률 P(y = i|y = i또는j, x)의 추정치 r_ij를 얻은 후에, 이러한 r_ij들을 사용하여 클래스 확률 p_i = P(y = i|x), i = 1, …, k를 계산한다.

PKPD[16]는 클래스 확률 추정을 위해 식 (1)의 간단한 계산을 사용한다. 과 일반적으로 N개의 사건 E_j의 합집합 는 로 표현되며, 사건 E_j가 (y = i 또는 y = j|x)라면 E_m∧E_n는 사건 (y = i|x)라는 것을 이용하여 다음 식을 얻는다.

반복계산으로 클래스 확률을 구하는 HT[17]는 r_ij와 u_ij = p_i/(p_i + p_j)간의 다음의 Kullback-Leibler 거리

를 최소화한다. 단, n_ij는 클래스 i와 j에 속하는 학습 자료의 개수이다. 식 (2) 의 최소화를 위해 편미분 값이 0이 되는 인 p_i들을 그림 1의 알고리즘으로 구한다.

WLW[18]는 p_i/(p_i + p_j ≈ r_ij이므로 r_jip_i≈ r_ijp_j인것을 이용하여 클래스 확률을 추정한다. 를 만족하면서 을 최소화하는 그림 2의 알고리즘을 사용한다.

다중클래스 확률추정을 위해서 오류정정 출력코드를 사용할 수 있다[22]. 오류정정 출력코드는 여러 다중클래스 분류의 개념을 포괄하는 일반적 방법이다[19-21]. 이 방법에서는 k개의 클래스를 가진 다중클래스 분류에서 각각의 클래스를 코딩행렬 M ∈{ −1, 0, 1}^k×l의 하나의 행과 연관시킨다.

학습과정에서는 코딩행렬의 각 열 i마다 이진분류기 f_i를 학습시킨다. 각 열에서 값이 0인 위치의 행에 대응하는 클래스의 자료는 학습에 사용하지 않고, 1에 대응되는 클래스의 자료는 양성 자료로 사용되고, −1에 대응되는 클래스의 자료들은 음성 자료로 사용한다. 따라서 오류정정 출력코드의 관점에서 쌍별 비교는 각열에서 한 원소는 1이고, 또 다른 원소는 −1이고, 나머지는 모두 0이다. 서로 구별되게 열을 만들 수 있는 방법이 k(k−1)/2개 이므로 모든 열의 개수는 l = k(k−1)/2이다; 두개의 위치에서 1과 −1이 서로 바뀐 것은 같은 이진분류로 간주한다. 일대전부(one versus all) 분류는 각 열에서 하나만 1이고 나머지는 모두 −1이므로 가능한 열의 개수 l = k이다. Dense 방법[20]의 경우에는 무작위로 열벡터 원소의 반은 1로 나머지는 −1로 구성하는 방법으로 l = 10log₂^k가 주로 사용된다. Sparse 방법[20]의 경우에는 무작위로 열벡터 원소의 1/4은 1로, 또 다른 1/4은 −1로, 나머지는 0으로 구성하는 방법으로 l = 15log₂^k가 주로 사용된다. 코딩행렬의 각 행의 거리가 커야 분류에 효율적이므로, Dense와 Sparse의 경우에는 무작위로 만들어진 코딩행렬에서 다음 거리[20]가 최대인 행렬이 선택된다.

단, i, j는 코딩행렬의 행이고, 는 코딩행렬 i행, d열 원소이고, sign(z)는 z>0이면 0, z<0이면 −1, z=0이면 0이다. Sparse 방법[21]은 다음의 거리를 사용하는 행렬의 원소가 0인 것을 고려한다.

오류정정 출력코드를 사용한 분류 과정에서는, 입력 자료 x에 대하여 l개의 이진분류기의 분류결과들로(f₁(x), …, f_l(x))을 구성하고, 이것과 코딩 행렬 M의 각 행을 비교하여 거리가 가장 가까운 행에 해당하는 클래스로 분류한다.

본 논문에서는 오류정정 출력코드를 사용한 클래스 확률 추정을 위해 GBT(Generalized Bradley-Terry model)[22]를 적용하였다. 이 방법은 코딩행렬의 각 열 i에서 +1로 표시된 행번호 집합을 , −1로 표시된 행번호 집합을 , 로 나타내고, , 로 정의한다. 또한, j∈ I_i인 행들과 연관된 클래스들에서 와 연관된 클래스들이 예측될 확률 모델을 로 가정한다. 클래스 예측확률은 를 최소화하는 p_j들을 구한다. 여기서 와 는 각각 와 와 관련된 클래스로 분류되는 개수이고, 코딩행렬의 열 i에 따라 구성된 이진분류기의 분류결과에서 얻어진다. 다음은 l(p)를 최소화하는 알고리즘이다.

본 논문에서는 단백질이 존재하는 세포내의 다중 위치를 예측하므로, 효과적인 다중레이블 분류방법이 필요하다. 따라서 관련연구로부터 단백질 세포내 위치 예측에 성능이 높다고 알려진 레이블 멱집합 방법을 변형하여 이용한다. 레이블 멱집합 방법은 다중레이블을 새로운 클래스로 정의하고, 다중클래스 분류를 사용하여 다중레이블을 예측한다. 앙상블 방법인 EPS는 레이블 멱집합 방법을 여러 번 수행하여 예측된 다중레이블들에 포함된 단일레이블들의 개수를 구하고, 이 개수가 문턱치보다 크면 예측된 것으로 판정한다. 본 논문에서는 레이블 멱집합과 마찬가지로 다중레이블을 예측하지만, 분류과정에서 다중레이블의 예측 확률을 추정하고, 추정한 예측 확률을 바탕으로 다중레이블에 포함된 단일레이블을 예측한다. 따라서 EPS처럼 예측된 단일 레이블의 개수만을 고려하지 않고 확률 정보를 이용하여 보다 정교한 예측이 가능하다.

제안한 방법은 학습의 첫 단계에서는 레이블 멱집합 분류기를 학습할 수 있을 정도의 자료 개수를 가진 다중레이블을 선정하여, 이후의 학습과 분류에 사용한다. 즉, 학습 자료에 f(5 사용)보다 많은 사례와 관련된 다중레이블 y₁,y₂,···y_R을 선택한다. 학습의 두 번째 단계에서는 다중레이블 y₁,y₂,···y_R에 관련된 학습 자료들만을 사용하여 R개의 클래스를 가진 다중클래스 분류기를 구성한다.

예측의 첫 단계에서는 II장에서 알아본 PKPD, HT, WLW와 같은 쌍별 비교를 사용한 다중클래스 예측 확률 추정 방법과 오류정정 출력코드의 관점에서 GBT를 사용하여 다중클래스 예측 확률을 추정한다. 즉, 각 평가 자료가 각각 y₁,y₂,···y_R 다중레이블로 분류될 확률 p₁,p₂,···p_R을 추정한다. 예측의 두 번째 단계에서는 추정된 예측 확률로서 가중치를 주어 예측된 다중레이블을 더하고, 문턱치 이상의 값을 갖는 단일 레이블을 최종적인 예측 결과를 결정한다. 즉, 학습 자료에 나타나는 모든 단일 레이블 집합을 L = {λ₁,λ₂…,λ_Q} 로 나타낼 때, 다중레이블 y_i들은 (0110 ··· 0)^T 같은 형태로 0과 1로 구성되고, k번째 값은 레이블 λ_k가 다중레이블의 원소이면 1이고, 그렇지 않으면 0이다. 식 (5)를 사용하여 단일레이블들의 예측 확률을 계산한다.

최종적인 분류는 간단한 수식 (6)을 사용하여, 미리 정해진 확률 문턱치 보다 큰 단일레이블로 결정하였다. 즉, 확률 벡터 p에서 정해진 문턱치 p_th보다 큰 값들이 위치하는 차원의 단일레이블들을 최종적인 결과이다.

제안한 방법은 식 (5)에서 보듯이, 높은 예측 확률 p_k를 가진 다중레이블들에 여러 차례 속하는 단일레이블의 예측확률은 강화되며, y₁,y₂,···y_R 다중레이블이외의 학습 자료에 나타나지 않은 다중레이블의 형태도 예측할 수 있는 장점이 있다. 또한, 제안한 방법은 단일레이블의 구성이 유사한 다중레이블이 예측되었을 때의 확률정보를 사용하여 각 단일레이블의 예측확률을 구한다. 제안한 방법은 앙상블 방법처럼 여러 번의 예측을 수행하지 않고, 여러 다중레이블의 예측 결과를 통합할 수 있다. 또한, 앙상블 방법으로 제안한 방법을 여러 번 수행하여 최종 예측결과를 얻도록 확장할 수 있다.

이 장에서는 단백질의 세포내 다중위치 예측에 대하여 다중레이블 분류방법들의 성능을 비교한다. 본 논문에서 제안한 방법은 클래스 확률추정 방법으로 쌍별 비교 방법인 PKPD[16], HT[17], WLW[18]를 사용하였고, 또 다른 확률추정 방법으로 GBT[22]를 사용하였는데, 오류정정 출력코드의 코딩행렬의 형태로서 쌍별 비교, 일대전부, Sparse를 사용하였고, Sparse는 개선된 코딩행렬 구성방법[21]도 적용하였다. 오류정정 출력코드에서 Dense 방법은 쌍별 비교, Sparse, 개선된 Sparse보다 성능이 높지 않고[20-21], 실험에 훨씬 많은 시간이 필요하므로 비교에서 제외하였다.

실험에는 14개의 세포내 위치 (centriole, cytoplasm, cytoskeleton, endoplasmic reticulum, endosome, extracell, golgi apparatus, lysosome, microsome, mitochondrion, nucleus, peroxisome, plasma membrane, synapse)로 구성된 인간 단백질 자료[1-5]를 사용하였다. 이 자료에서 2,580개 단백질은 하나의 세포내 위치, 480개는 두 개의 위치, 43개는 3개의 위치, 3개는 4개의 위치에 동시에 존재하며, 25% 이하의 적은 단백질 서열 동일성을 가지므로, 기본적인 서열 유사성만으로는 단백질의 세포내 위치 예측이 어려운 자료이다. 분류실험에는 자료를 균등하게 5개로 나누어, 하나는 평가에 사용하고 나머지 4개는 학습 자료로 사용하는 방법을 5회 반복하는 5겹 교차검증(fivefold cross-validation)을 사용하였다.

분류기의 특징벡터는 각 단백질 서열과 가장 유사한 단백질을 유전자 온톨로지를 가진 단백질 데이터베이스(http://www.ebi.ac.uk/GOA)에서 찾아, 그것의 유전자 온톨로지를 사용하는 방법을 사용하였다[1,2,4-7,9, 23]. 유전자 온톨로지는 분자적 기능, 생물학적 과정, 세포 요소의 관점에서 특징화한 용어로 유전자를 표현한 것으로, 각 단백질의 특징을 표현할 수 있다. 단백질의 세포내 위치에 따라 보다 판별력이 높게 나타내는 유전자 온톨로지를 가중하는 방법[23]을 사용하였고, 가장 유사한 두 개의 서열에서 나타나는 유전자 온톨로지의 빈도를 이용하는 방법[9]을 사용하였다.

분류 방법의 성능 평가는 예측된 다중레이블이 실제 다중레이블과 일부만 일치하는 경우를 고려하는 다중레이블 분류의 평가 척도를 사용한다[11-13]. 다중레이블 평가척도에서 부록의 식 (S1)~(S6)의 사례기반 방법은 각 사례에 대해 실제 레이블과 예측된 레이블간의 차이를 평균하고, 식 (S7)~(S12)의 레이블기반 방법은 각각의 레이블에 대해서 예측성능을 구한다. 식 (S13)은 평가척도들을 합해 간략한 비교가 가능하게 한다[9].

본 논문과 같은 실험 자료를 사용하는 논문[3]에서는 최근접-이웃 분류기들을 조합하는 Hum-mPLOC 2.0[1]은 recall, F₁, subset_accuracy가 0.519, 0.541, 0.294이고, 가우시안 과정 모델과 공분산 행렬로 레이블간의 연관성을 표현하는 방법[3]은 0.643, 0.506, 0.202로 성능이 전반적으로 저조하다. 세포내 위치의 모든 쌍들에 대한 분류기를 구성하여 분류결과를 투표하는 방법[14]는 subset_accuracy가 0.45이하이다. 분류체인 앙상블 방법인 ECC[14]를 사용하는 방법[5]은 accuracy, precision, recall, F₁값이 0.7913, 0.8249, 0.8404, 0.8191로 성능이 상대적으로 우수하다.

표 1의 ECC, EPS는 Mulan 라이브러리[24]를 사용한 결과[9]로서, 이전 연구 결과[5]와 유사하다. 본 논문에서 제안한 PCML(Probabilistic Combination of Multi- Labels)은 클래스 확률추정으로 PKPD를 사용한 결과 이며, 대부분의 평가 척도에서 ECC나 EPS보다 높은 성능을 보였다.　EPS와 ECC의 성능을 비교해보면, precision, macro_precision, micro_precision은 EPS가 좋은 반면에, recall, macro_recall, micro_recall은 ECC가 좋다. precision, macro_precision, micro_precision의 정의에서는 분모의 fp(false positive)가 자료와 관련 되지 않은 레이블이 예측되면 평가척도의 값이 작아진다. 하지만, recall, macro_recall, micro_recall은 fp를 고려하지 않고, 관련된 레이블이 예측이 잘 되었는지를 측정한다. PCML은 EPS와 같은 레이블멱집합 방법을 사용하므로, EPS의 장점처럼 fp가 커지지 않아 precision, macro_precision, micro_precision은 정확도를 유지하면서, recall, macro_recall, micro_recall을 크게 향상시켰다.

PCML에서 레이블 멱집합 분류기를 구현하기 위하여 LIBSVM[25]을 사용하였고, 가우시안 커널의 𝛾 =0.001, 0.01, 0.1, 1, 비용 파라미터 C =0.1, 1, 10, 100을 사용하였다. 또한, 식 (6)의 확률문턱치 p_th=0.25, 0.27, 0.29, 0.31, 0.33, 0.35을 사용하여, 다중클래스 확률추정 방법들의 성능을 조사하였다. 표 2에서 쌍별 비교를 사용하는 다중클래스 확률추정인 PKPD, HT, WLW와 오류정정 출력코드를 사용하는 방법인 1vs1(쌍별 비교), 1vsAll(일대전부), Sparse, SparseT를 비교하였다. Sparse와 SparseT의 경우에는 무작위로 코딩행렬 10,000개를 생성한 후에, Sparse는 식 (3), SparseT는 식 (4)를 최대화하는 행렬을 선택하였다. 표 2는 여러 다중클래스 확률 추정에서 가장 높은 S-measure일 때의 파라미터 𝛾, C, p_th를 나타낸다.

표 3은 표 2에의 파라미터를 사용한 PKPD, WLW, Sparse, SparseT의 성능을 여러 평가척도로 나타내었다. Sparse가 가장 높은 S-measure를 보이고 recall과 F₁과 관련된 평가척도에서 커다란 성능향상을 보였으나, precision과 관련된 평가척도에 대해서는 성능향상이 적었다. SparseT는 recall, F₁,precision과 관련된 평가척도에 대해서 전반적으로 성능이 향상되었다. PKPD는 precision과 관련된 평가척도에 대해서 좋은 성능을 보이고, 나머지 평가척도들에 대해서는 Sparse나 SparseT보다 성능이 떨어졌다. WLW는 대체적으로 다른 방법들보다 성능이 좋지 않다.

본 논문에서는 단백질의 다중 세포내 위치 예측에 적합한 다중레이블 분류방법을 제안하였다. 첫 번째로 레이블간의 연관관계를 효과적으로 모델링할 수 있는 다중레이블 분류방법이 다중 세포내 위치를 보다 정확하게 예측할 수 있다는 점을 이용하였다. 본 논문에서는 레이블 멱집합 방법처럼 다중레이블 자체를 하나의 단일레이블로 구성하였다. 두 번째로 단백질 세포내 다중위치 자료는 각 다중레이블들에 대한 학습 자료가 충분하지 않으므로, 앙상블 방법을 이용하는 대신에, 각기 다른 확률로 예측된 여러 다중레이블을 동시에 고려하여, 중복된 단일레이블의 예측확률을 얻었다. 각 다중레이블에 대한 정확한 예측확률을 구하기 위하여 여러가지 다중클래스 확률 추정 방법을 적용하였다.

제안한 PCML방법은 단백질 세포내 위치예측에 효과적인 EPS와 ECC보다 대부분의 평가척도에서 우수 하였고, 제안한 방법에 적용한 다중클래스 확률 추정 방법에서 PKPD와 Sparse, SparseT가 효과적이었다.

본 논문에서는 최종적인 분류 방법으로 간단한 확률 문턱치를 사용하였는데, 이후에는 각 단일레이블의 특성을 고려하여 문턱치를 구성하고, 앙상블 방법을 추가적으로 적용할 예정이다. 또한, 제안한 방법을 동물, 식물, 곰팡이, 바이러스 등의 여러 영역의 세포내 위치 예측에 적용할 계획이다.