유사도 측정

통계학 및 관련 분야에서 유사도 측정(영어: Similarity measure), 유사도 함수(영어: similarity function) 또는 유사도 지표(영어: similarity metric)는 두 개체 간의 유사성을 정량화하는 실수 값 함수이다. 유사성에 대한 단일 정의는 없지만, 일반적으로 이러한 측정값은 어떤 의미에서 거리 함수의 역이다. 즉, 유사한 개체에 대해서는 큰 값을 가지며, 매우 다른 개체에 대해서는 0 또는 음수 값을 가진다. 하지만 더 넓은 의미에서 유사도 함수는 거리 공리를 만족할 수도 있다.

코사인 유사도는 실수 값 벡터에 일반적으로 사용되는 유사도 측정값으로, 정보 검색 분야(다른 분야에서도 사용됨)에서 벡터 공간 모델의 문서 유사성을 평가하는 데 사용된다. 기계 학습에서 방사 기저 함수 커널과 같은 일반적인 커널 함수는 유사도 함수로 볼 수 있다.^[1]

다양한 유사도 측정 공식의 사용

비교 대상에 따라 다양한 유형의 객체에 대해 다양한 유사도 측정 유형이 존재한다. 각 객체 유형에는 다양한 유사도 측정 공식이 있다.^[2]

두 데이터 포인트 간의 유사도

두 데이터 포인트 간의 유사성을 찾는 데에는 여러 가지 옵션이 있으며, 그중 일부는 다른 유사성 방법의 조합이다. 두 데이터 포인트 간의 유사성 측정 방법에는 유클리드 거리, 맨해튼 거리, 민코프스키 거리, 체비쇼프 거리가 포함된다. 유클리드 거리 공식은 평면상의 두 점 사이의 거리를 찾는 데 사용되며, 아래 이미지에 시각화되어 있다. 맨해튼 거리는 두 주소 사이의 최단 경로를 찾는 데 사용할 수 있으므로 GPS 응용 프로그램에서 흔히 사용된다. 유클리드 거리 공식과 맨해튼 거리 공식을 일반화하면 다양한 응용 분야에서 사용할 수 있는 민코프스키 거리 공식이 남는다.

문자열 간의 유사도

문자열을 비교하기 위해 사용할 수 있는 다양한 문자열 측정이 있다. 이러한 방법에는 편집 거리, 레벤슈타인 거리, 해밍 거리, 자로 거리가 포함된다. 최적의 공식은 응용 프로그램의 요구 사항에 따라 달라진다. 예를 들어, 편집 거리는 철자 검사 등 자연어 처리 응용 프로그램 및 기능에 자주 사용된다. 자로 거리는 기록 연결에서 이름과 성을 다른 소스와 비교하는 데 일반적으로 사용된다.

두 확률 분포 간의 유사도

확률 분포에 대한 일반적인 유사도 측정값은 바타차리아 거리와 헬링거 거리이다. 둘 다 동일한 도메인에서 두 확률 분포의 유사성을 정량화하며, 수학적으로 밀접하게 연결되어 있다. 바타차리아 거리는 삼각 부등식을 만족하지 않아 거리 공간을 형성하지 않는다. 헬링거 거리는 확률 분포 공간에 대한 거리를 형성한다.

두 집합 간의 유사도

자카드 지수 공식은 두 집합 간의 유사성을 측정하는데, 이는 두 집합에 모두 존재하는 항목 수를 전체 항목 수에 비례하여 계산한다. 이 공식은 추천 시스템 및 소셜 미디어 분석에 흔히 사용된다. 쇠렌센-다이스 계수 또한 두 집합에 있는 항목 수를 전체 항목 수와 비교하지만, 공유 항목 수에 대한 가중치가 더 크다. 쇠렌센-다이스 계수는 생물학 응용 분야에서 두 유전자 또는 종 집합 간의 유사성을 측정하는 데 흔히 사용된다.

두 시퀀스 간의 유사도

시계열을 비교할 때, 일부 유사도 측정은 완전히 정렬되지 않은 두 시퀀스의 유사도를 추가로 고려해야 한다.

동적 시간 워핑

군집화에서의 사용

군집화 또는 클러스터 분석은 유사한 객체들을 함께 그룹화하여 데이터에서 패턴을 발견하는 데 사용되는 데이터 마이닝 기술이다. 이는 데이터 포인트 집합을 유사성을 기반으로 그룹 또는 클러스터로 분할하는 과정을 포함한다. 군집화의 근본적인 측면 중 하나는 데이터 포인트 간의 유사성을 측정하는 방법이다.

유사도 측정은 많은 군집화 기술에서 중요한 역할을 한다. 이는 두 데이터 포인트가 얼마나 밀접하게 관련되어 있는지, 그리고 동일한 클러스터로 그룹화되어야 하는지 여부를 결정하는 데 사용되기 때문이다. 유사도 측정은 군집화되는 데이터 유형과 해결하려는 특정 문제에 따라 다양한 형태를 가질 수 있다.

가장 일반적으로 사용되는 유사도 측정 중 하나는 유클리드 거리이며, 이는 K-평균 알고리즘 및 계층적 군집화를 포함한 많은 군집화 기술에서 사용된다. 유클리드 거리는 고차원 공간에서 두 점 사이의 직선 거리를 측정하는 것이다. 이는 두 점의 해당 좌표 간의 제곱 차이의 합의 제곱근으로 계산된다. 예를 들어, 두 데이터 포인트 $(x_{1},y_{1})$ 와 $(x_{2},y_{2})$ 가 있는 경우, 이들 사이의 유클리드 거리는 $d=\surd [(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}]$ 이다.

또 다른 흔히 사용되는 유사도 측정은 자카드 지수 또는 자카드 유사도로, 이는 존재/부재 데이터^[3] 또는 불리언 데이터와 같은 이진 데이터로 작업하는 클러스터링 기술에 사용된다. 자카드 유사도는 텍스트 데이터로 작업하는 클러스터링 기술에 특히 유용하며, 공유 기능 또는 키워드를 기반으로 유사한 문서 클러스터를 식별하는 데 사용될 수 있다.^[4] 이는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 계산된다. $J(A,B)={A\bigcap B \over A\bigcup B}$ .

162개의 관련 핵 프로파일 간의 유사도는 자카드 유사도 측정을 사용하여 테스트된다(히트맵이 있는 그림 참조). 핵 프로파일의 자카드 유사도는 0에서 1까지 범위이며, 0은 두 집합 간의 유사성이 없음을 나타내고 1은 가장 유사한 핵 프로파일을 클러스터링하는 것을 목표로 완벽한 유사성을 나타낸다.

맨해튼 거리로도 알려진 맨해튼 거리는 연속 데이터로 작업하는 클러스터링 기술에서 일반적으로 사용되는 유사도 측정이다. 이는 고차원 공간에서 두 데이터 포인트 사이의 거리를 측정하는 것으로, 두 포인트의 해당 좌표 간의 절대 차이의 합으로 계산된다 $\left\vert x_{1}-x_{2}\right\vert +\left\vert y_{1}-y_{2}\right\vert$ .

명목형, 순서형, 수치형 속성을 포함한 혼합형 데이터의 경우, 고워 거리(또는 유사도)가 일반적으로 사용되는 선택이다. 이는 다양한 유형의 변수를 암묵적으로 처리할 수 있기 때문이다. 이 방법은 먼저 각 객체 내에서 변수 쌍 간의 유사도를 계산한 다음, 이러한 유사도들을 결합하여 객체 쌍당 단일 가중 평균을 구한다. 따라서 $p$ 개의 기술자를 갖는 두 객체 $i$ 와 $j$ 에 대해 유사도 $S$ 는 다음과 같이 정의된다. $S_{ij}={\frac {\sum _{k=1}^{p}w_{ijk}s_{ijk}}{\sum _{k=1}^{p}w_{ijk}}},$ 여기서 $w_{ijk}$ 는 음이 아닌 가중치이며 $s_{ijk}$ 는 $k$ -번째 변수에 대한 두 객체 간의 유사도이다.

스펙트럼 군집화에서 유사도 또는 친화도 측정은 데이터 분포 형태의 비볼록성과 관련된 어려움을 극복하기 위해 데이터를 변환하는 데 사용된다.^[5] 이 측정은 $n$ 개의 점 집합에 대해 $(n,n)$ 크기의 유사도 행렬을 생성하며, 행렬의 $(i,j)$ 항목은 단순히 $i$ 와 $j$ 사이의 유클리드 거리(의 역수)일 수도 있고, 가우스 $e^{-\|s_{1}-s_{2}\|^{2}/2\sigma ^{2}}$ 와 같은 더 복잡한 거리 측정일 수도 있다.^[5] 이 결과를 네트워크 분석 기술로 추가 수정하는 것도 일반적이다.^[6]

유사도 측정값의 선택은 클러스터링되는 데이터 유형과 해결되는 특정 문제에 따라 달라진다. 예를 들어, 유전자 발현 데이터와 같은 연속 데이터로 작업하는 경우 유클리드 거리 또는 코사인 유사도가 적절할 수 있다. 핵 프로필에서 게놈 위치의 존재와 같은 이진 데이터로 작업하는 경우 자카드 지수가 더 적절할 수 있다. 마지막으로, 이미지 또는 신호 처리 데이터와 같이 그리드 또는 격자 구조로 배열된 데이터로 작업하는 경우 맨해튼 거리가 클러스터링에 특히 유용하다.

서열 정렬에서의 사용

유사도 행렬은 서열 정렬에 사용된다. 더 유사한 문자에 더 높은 점수가 주어지고, 유사하지 않은 문자에는 더 낮거나 음의 점수가 주어진다.

뉴클레오타이드 유사도 행렬은 핵산 서열을 정렬하는 데 사용된다. DNA에서 일반적으로 발견되는 뉴클레오타이드는 아데닌 (A), 사이토신 (C), 구아닌 (G), 티민 (T) 4개뿐이므로 뉴클레오타이드 유사도 행렬은 단백질 유사도 행렬보다 훨씬 간단하다. 예를 들어, 간단한 행렬은 동일한 염기에 +1점, 동일하지 않은 염기에 -1점을 할당한다. 더 복잡한 행렬은 전이(C 또는 T와 같은 피리미딘에서 다른 피리미딘으로, 또는 A 또는 G와 같은 퓨린에서 다른 퓨린으로의 변화)에 대해 전위(피리미딘에서 퓨린으로 또는 그 반대로)보다 더 높은 점수를 부여한다. 행렬의 일치/불일치 비율은 목표 진화 거리를 설정한다.^[8]^[9] BLASTN에서 사용되는 +1/-3 DNA 행렬은 99% 동일한 서열 간의 일치를 찾는 데 가장 적합하다. +1/-1 (또는 +4/-4) 행렬은 약 70% 유사성을 가진 서열에 훨씬 더 적합하다. 유사성이 낮은 서열에 대한 행렬은 더 긴 서열 정렬을 필요로 한다.

아미노산 유사도 행렬은 더 복잡하다. 유전 부호에 의해 암호화되는 아미노산이 20개이므로 가능한 치환의 수가 더 많기 때문이다. 따라서 아미노산에 대한 유사도 행렬은 400개의 항목을 포함한다(보통 대칭행렬이지만). 첫 번째 접근 방식은 모든 아미노산 변화에 동일한 점수를 부여했다. 나중에 아미노산 유사도는 코돈을 해당 아미노산으로 변경하는 데 필요한 염기 변화 수를 기반으로 결정하도록 정교화되었다. 이 모델은 더 낫지만, 아미노산 변화의 선택 압력을 고려하지는 않는다. 더 나은 모델은 아미노산의 화학적 특성을 고려했다.

한 가지 접근 방식은 유사도 행렬을 경험적으로 생성하는 것이다. 마거릿 오클리 데이호프 방법은 계통 발생 트리와 트리에서 얻은 서열을 사용했다. 이 접근 방식은 점 돌연변이 수용 행렬 시리즈를 탄생시켰다. PAM 행렬은 100개의 아미노산당 얼마나 많은 뉴클레오타이드 변화가 발생했는지에 따라 레이블이 지정된다. PAM 행렬은 잘 이해된 진화 모델을 가지고 있다는 이점이 있지만, 짧은 진화 거리(PAM10-PAM120)에서 가장 유용하다. 긴 진화 거리, 예를 들어 PAM250 또는 20% 동일성에서는 BLOSUM 행렬이 훨씬 더 효과적이라는 것이 입증되었다.

BLOSUM 시리즈는 여러 분기된 서열을 비교하여 생성되었다. BLOSUM 시리즈는 모든 서열 사이에 돌연변이되지 않고 남아 있는 엔트로피 양에 따라 레이블이 지정되므로, BLOSUM 번호가 낮을수록 PAM 번호가 높다.

같이 보기

각주

↑ Vert, Jean-Philippe; Tsuda, Koji; Schölkopf, Bernhard (2004). 〈A primer on kernel methods〉 (PDF). 《Kernel Methods in Computational Biology》.
↑ “Different Types of Similarity measurements”. OpenGenus.
↑ Chung, Neo Christopher; Miasojedow, BłaŻej; Startek, Michał; Gambin, Anna (2019). 《Jaccard/Tanimoto similarity test and estimation methods for biological presence-absence data》 (영어). 《BMC Bioinformatics》 20. 644쪽. doi:10.1186/s12859-019-3118-5. ISSN 1471-2105. PMC 6929325. PMID 31874610.
↑ 《International MultiConference of Engineers and Computer Scientists : IMECS 2013 : 13-15 March, 2013, the Royal Garden Hotel, Kowloon, Hong Kong》. S. I. Ao, International Association of Engineers. Hong Kong: Newswood Ltd. 2013. ISBN 978-988-19251-8-3. OCLC 842831996.
↑ ^가 ^나 Ng, A.Y.; Jordan, M.I.; Weiss, Y. (2001), “On Spectral Clustering: Analysis and an Algorithm”, 《Advances in Neural Information Processing Systems》 (MIT Press) 14: 849–856
↑ Li, Xin-Ye; Guo, Li-Jie (2012), “Constructing affinity matrix in spectral clustering based on neighbor propagation”, 《Neurocomputing》 97: 125–130, doi:10.1016/j.neucom.2012.06.023
↑ Bondarenko, Kirill (2019), 《Similarity metrics in recommender systems》, 2023년 4월 25일에 확인함
↑ States, D; Gish, W; Altschul, S (1991). 《Improved sensitivity of nucleic acid database searches using application-specific scoring matrices》. 《Methods: A Companion to Methods in Enzymology》 3. 66쪽. CiteSeerX 10.1.1.114.8183. doi:10.1016/S1046-2023(05)80165-3.
↑ Sean R. Eddy (2004). 《Where did the BLOSUM62 alignment score matrix come from?》 (PDF). 《Nature Biotechnology》 22. 1035–6쪽. doi:10.1038/nbt0804-1035. PMID 15286655. S2CID 205269887. 2006년 9월 3일에 원본 문서 (PDF)에서 보존된 문서.

F. Gregory Ashby; Daniel M. Ennis (2007). 《Similarity measures》. 《Scholarpedia》 2. 4116쪽. Bibcode:2007SchpJ...2.4116A. doi:10.4249/scholarpedia.4116.

[primer-1] Vert, Jean-Philippe; Tsuda, Koji; Schölkopf, Bernhard (2004). 〈A primer on kernel methods〉 (PDF). 《Kernel Methods in Computational Biology》.

[2] “Different Types of Similarity measurements”. OpenGenus.

[3] Chung, Neo Christopher; Miasojedow, BłaŻej; Startek, Michał; Gambin, Anna (2019). 《Jaccard/Tanimoto similarity test and estimation methods for biological presence-absence data》 (영어). 《BMC Bioinformatics》 20. 644쪽. doi:10.1186/s12859-019-3118-5. ISSN 1471-2105. PMC 6929325. PMID 31874610.

[4] 《International MultiConference of Engineers and Computer Scientists : IMECS 2013 : 13-15 March, 2013, the Royal Garden Hotel, Kowloon, Hong Kong》. S. I. Ao, International Association of Engineers. Hong Kong: Newswood Ltd. 2013. ISBN 978-988-19251-8-3. OCLC 842831996.

[Ng-5] 가 ^나 Ng, A.Y.; Jordan, M.I.; Weiss, Y. (2001), “On Spectral Clustering: Analysis and an Algorithm”, 《Advances in Neural Information Processing Systems》 (MIT Press) 14: 849–856

[6] Li, Xin-Ye; Guo, Li-Jie (2012), “Constructing affinity matrix in spectral clustering based on neighbor propagation”, 《Neurocomputing》 97: 125–130, doi:10.1016/j.neucom.2012.06.023

[Bondarenko-7] Bondarenko, Kirill (2019), 《Similarity metrics in recommender systems》, 2023년 4월 25일에 확인함

[8] States, D; Gish, W; Altschul, S (1991). 《Improved sensitivity of nucleic acid database searches using application-specific scoring matrices》. 《Methods: A Companion to Methods in Enzymology》 3. 66쪽. CiteSeerX 10.1.1.114.8183. doi:10.1016/S1046-2023(05)80165-3.

[9] Sean R. Eddy (2004). 《Where did the BLOSUM62 alignment score matrix come from?》 (PDF). 《Nature Biotechnology》 22. 1035–6쪽. doi:10.1038/nbt0804-1035. PMID 15286655. S2CID 205269887. 2006년 9월 3일에 원본 문서 (PDF)에서 보존된 문서.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

다양한 유사도 측정 공식의 사용

군집화에서의 사용

추천 시스템에서의 사용

서열 정렬에서의 사용

같이 보기

각주