정규화된 압축 거리

정규화된 압축 거리(NCD)는 문서 2개, 편지 2개, 이메일 2개, 음악 점수 2개, 언어 2개, 프로그램 2개, 사진 2개, 시스템 2개, 게놈 2개 등 두 개체의 유사성을 측정하는 방법이다. 이러한 측정은 적용에 의존하거나 임의로 해서는 안 된다. 두 물체의 유사성에 대한 합리적인 정의는 두 물체를 서로 변형시키는 것이 얼마나 어려운가 하는 것이다.

클러스터 분석을 위한 정보 검색 및 데이터 마이닝에 활용할 수 있다.

정보 거리

우리는 한 사람이 말하는 물체가 0과 1의 유한 문자열이라고 가정한다. 따라서 우리는 끈 유사성을 의미한다. 모든 컴퓨터 파일은 이런 형태, 즉, 어떤 물체가 컴퓨터의 파일이라면 이런 형태다. $문자열{\displaystyle }$ $x{\displaystyle }$ ${\displaystyle x}$과 $y{\displaystyle }$ ${\displaystyle$ y$}$ 사이의 $정보$ 거리를 y ${\displaystyle$ y$}$에서 x ${\displaystyle$ x}을$$(를) 계산하는 최단 프로그램$$$$$$p {\$displaystyle$ p}의 길이로 정의할$$ 수 있다. 이 최단 프로그램은 고정 프로그래밍 언어로 되어 있다. 기술적인 이유로 튜링 머신의 이론적 개념을 사용한다. 더욱이 $p{\displaystyle }$ ${\displaystyle p}$의 길이를 표현하기 위해서는 Kolmogorov 복잡성의 개념을 사용한다$$. 그리고 나서, 그것은 보여졌다.

${\displaystyle p =\max\{K(x\mid y), K(y\mid x)\}}$

무시될 수 있는 로그 첨가 용어까지. 이 정보 거리는 미터법(로그 적층 용어까지의 메트릭 불평등을 충족함), 범용(예를 들어 형상에서 일정한 적층 용어까지 계산된 모든 계산 가능한 거리를 경미화함)^[1]으로 표시된다.

정규화된 정보 거리(유사성 메트릭)

정보 거리는 절대적이지만 유사성을 표현하려면 상대적인 것에 더 관심을 갖는다. 예를 들어, 길이 1,000,000의 두 문자열이 1000비트만큼 차이가 난다면, 우리는 그 문자열이 1000비트만큼 다른 1000비트의 두 문자열보다 상대적으로 더 비슷하다고 생각한다. 따라서 우리는 유사성 지표를 얻기 위해 정상화할 필요가 있다. 이 방법으로 정규화된 정보 거리(NID)를 얻는다.

${\displaystyle NID(x,y)={\frac {\max\{K{(x\mid x)}\}}{\max\{K(x), K(y)\}}}}$

여기서 $K{\displaystyle (x}$ ${\displaystyle \mid }$ y${\displaystyle }$) ${\displaystyle K(x\mid y)}$은 $y{\displaystyle }$ ${\displaystyle y}$이(가) 입력으로$$ 지정된$$ x ${\displaystyle x}$의 알고리즘 정보다. NID는 ${\displaystyle \mathrm{NI}}$ ${\displaystyle D(x}$, y$){\displaystyle NID(x,y)}$라는 함수가 미터법 거리 측정에 대한 기본 요건을 만족하는 것으로 나타났기$$ 때문에 '유사성 메트릭'이라고 불린다.^[2][3] 그러나 계산이 가능하지도 않고 심지어 반투명도 가능하지도 않다.^[4]

정규화된 압축 거리

NID 메트릭은 계산할 수 없지만 응용 프로그램이 풍부하다. $Z{\displaystyle }$(${\displaystyle x}$) {\$displaystyle$Z($x$$)}$을(를$)$ 사용하여 실제 압축기에 $의해$ K ${\$displaystyle $K$$}$을(를) 약칭하면 NID를 적용하기 쉽도록 압축기 Z(예:^[2] "gzip", "bzip2, "PPMZ")로 압축한$$ 파일 $x{\displaystyle }$ ${\displaysty$ x$}$의 이진 길이입니다$$. Vitani와 Cilibrasi는 NID를 다시 작성하여 NCD(표준화된 압축 거리)를 얻는다.

${\displaystyle NCD_{Z}(x,y)={\frac {Z(xy)-\min\{Z(x)\}{\max\{Z(x), Z(y)\}}}}$^[3]

NCD는 실제로 압축기 Z와 파라메트리된 거리의 제품군이다. Z가 좋을수록 NCD가 NID에 가까이 접근할수록 결과가 좋아진다.^[3]

적용들

정규화된 압축 거리는 언어와 계통생성 나무를 완전히 자동으로 재구성하는 데 사용되어 왔다.^[2][3] 또한 일반 클러스터링의 새로운 애플리케이션과 임의 도메인의 자연 데이터 분류,^[3] 이기종 데이터의 클러스터링,^[3] 도메인 전체의 이상 징후 검출에도 사용할 수 있다.^[5] NID와 NCD는 네트워크 트래픽과 클러스터 컴퓨터 웜 및 바이러스, 저자 ^[6]귀인,^[3] 유전자 표현 역학, 유용성 대 쓸모없는 줄기 세포 예측,^[7][8][9] 중요 네트워크,^[10] 이미지 등록,^[11] 질의 응답 시스템 등을 분석하기 위해 음악 분류 등 수많은 과목에 적용되어 왔다.^[12]

퍼포먼스

데이터마이닝 커뮤니티의 연구자들은 NCD와 변형을 "변수 없는 특징 없는" 데이터 마이닝 도구로 사용한다.^[5] 한 그룹은 다양한 시퀀스 벤치마크에서 밀접하게 관련된 메트릭스를 실험적으로 테스트했다. 이들은 지난 10년간 7개 주요 데이터 마이닝 컨퍼런스에서 발견된 51가지 주요 방법과 압축 방식을 비교해 이질적인 데이터를 클러스터링하고 이상 징후를 탐지하는 압축 방식과 도메인 데이터의 클러스터링 경쟁력을 확립했다.

NCD는 소음에 강하다는 장점이 있다.^[13] 그러나 NCD가 "변수가 없는" 것처럼 보이지만, 실제적인 질문에는 NCD 계산에 사용할 압축기와 기타 가능한 문제가 포함된다.^[14]

NRC(표준화된 상대 압축)와의 비교

다른 문자열과 관련된 문자열의 정보를 측정하기 위해서는 상대적 반간격(NRC)에 의존할 필요가 있다.^[15] 대칭과 삼각 불평등 거리 특성을 존중할 필요가 없는 조치들이다. NCD와 NRC는 매우 유사해 보이지만 다른 문제를 다룬다. NRC는 다른 문자열의 정보를 사용하여 구성할 수 없는 대상 문자열의 분율을 나타내는 반면 NCD는 주로 정보 콘텐츠를 사용하여 두 문자열이 얼마나 유사한지 측정한다. 영장류 게놈의 진화에 대한 비교는 다음을 참조하십시오.^[16]

표준화된 Google 거리

물체는 쥐의 문자 그대로 4글자 게놈이나 톨스토이의 문자 그대로 전쟁과 평화의 문자처럼 주어질 수 있다. 단순성을 위해 우리는 그 물체의 모든 의미는 문자 그대로의 물체 그 자체로 표현된다고 생각한다. '쥐의 네 글자로 된 게놈'이나 '톨스토이의 전쟁과 평화'라는 글과 같은 물체도 이름별로 줄 수 있다. 또한 문자 그대로 주어질 수 없고, 이름만으로 주어질 수 없고, '집'이나 '빨간'처럼 인류의 배경 상식에 있는 문맥에서 그 의미를 습득하는 사물도 있다. 우리는 의미적 유사성에 관심이 있다. 구글이 웹에서 반환한 페이지 적중 횟수에서 얻은 코드 워드 길이를 이용해 NCD 공식을 이용해 의미적 거리를 얻고 구글을 데이터 마이닝, 텍스트 이해, 분류, 번역에 유용한 압축기로 본다. 표준화된 구글 거리(NGD)라고 불리는 관련 NCD는 다음과 같이 다시 쓸 수 있다.

${\displaystyle NGD(x,y)={\frac {\max\{\log f(x)}\log f(x,y)\}{\log N-\min\{\log f(x),\log f(y)\}}}}}}}$

$여기$서 f${\displaystyle }$( ${\displaystyle x}$) ${\$$displaystyle$ $f($$x)}$은(는)$$ 검색어 $x$를 포함하는 페이지 수를 나타내며$$$,$ $f{\displaystyle }$$($${\displaystyle x}$, y${\displaystyle }$) ${\$$displaystyle$ $f$$($$x,$$y)$는 구글이나$$agg를 반환할 수 있는 $검색{\displaystyle }$ 엔진에서 반환된 $x$를 모두 포함하는 페이지 수를 $나타낸다$.페이지수를 재등록하다 $숫자{\displaystyle }$ N$${\$displaystyle N}$은(는) 포함된 검색어 또는 구 수에 따라$$ 각 페이지를 세는 것이 더 적절하지만 인덱싱된 페이지 수로 설정할 수 있다. 엄지의 법칙으로 페이지 수를 천 단위로 곱할 수 있다.^[17]

참고 항목

• 벡터공간의 단어표현의 효율적 추정
• 워드2벡

참조

외부 링크

• M. Li와 P. 비타니, 뉴욕 스프링거-베를라그, 2019년 4월호, 콜모고로프 복잡성과 그 적용에 대한 소개