메도이드

메도이드(medoids)는 데이터 집합 또는 데이터 집합 내의 클러스터의 대표적인 개체로서, 클러스터 내의 모든 개체와의 불일치 합계가 최소다.^[1]메도이드들은 평균이나 중심체와 개념이 유사하지만, 항상 데이터 세트의 구성원으로 제한된다.메도이드들은 그래프와 같이 평균이나 중심을 정의할 수 없을 때 가장 일반적으로 데이터에 사용된다.또한 이미지, 3-D 궤적 및 유전자 표현^[2](데이터가 희박한 동안 메디오드는 필요하지 않음)과 같은 데이터 집합을 나타내지 않는 컨텍스트에서도 사용된다.이것들은 또한 유클리드 거리(예: 영화배율)를 제곱하지 않는 거리 이외의 거리를 사용하여 대표자를 찾기를 원하면서 흥미롭다.

일부 데이터 세트의 경우 중위수와 마찬가지로 둘 이상의 중위수가 있을 수 있다.medoid의 일반적인 적용은 k-medoids 군집화 알고리즘으로 k-means 알고리즘과 유사하지만 평균이나 중심이 정의될 수 없을 때 작동한다.이 알고리즘은 기본적으로 다음과 같이 작용한다.첫째, 메도이드 세트는 무작위로 선택된다.둘째, 다른 점까지의 거리가 계산된다.셋째, 데이터는 가장 유사한 물질에 따라 군집화된다.넷째, 중합체 세트는 반복 과정을 통해 최적화된다.

중위수, 기하학적 중위수 또는 중심과 같지 않은 점에 유의하십시오.중위수는 1차원 데이터에 대해서만 정의되며, 규범에 의해 유도된 측정 기준(맨해튼 거리 또는 유클리드 거리 등)의 다른 지점과의 차이를 최소화한다.기하학적 중위수는 어떤 차원에서도 정의되지만, 반드시 원래 데이터 집합 내에서부터의 점이라고 할 수는 없다.

정의

${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ { ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ 1, ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ x ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ x ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ ${\textstyle {\x}:=\{x_{1},x_{2},\dots,x_{n}\}}}}}$ 을(를) 거리 함수가 d인 공간에 ${\textstyle n}$ ${\textstyle$ n $}개$ 의 점 집합으로 ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ ${\textstyle n}$ 두도록 한다.Medoid는 다음과 같이 정의된다.

x_{\text{medoid}=\arg \min _{y\in {\mathcal{X}}\sum _{i=1}^{n1}d(y,x_{i}).

메도이드 계산 알고리즘

위의 정의에서 볼 때 앙상블에서 점 사이의 쌍방향 거리를 모두 계산한 후에 중원형을 계산할 수 있다는 것은 분명하다.이 작업에는 O ${\textstyle O(n^{2})}$ ( ${\textstyle O(n^{2})}$ 2 ${\textstyle O(n^{2})}$ ) {\ $textstyle O($ n^{ $2})}$ 의 거리 ${\textstyle O(n^{2})}$ 평가가 필요하다.최악의 경우 거리 평가가 적은 상태에서 중합체를 계산할 수 없다.^[3]^[4]그러나 서로 다른 통계적 모델에서 정확하거나 근사적으로 2분위 시간 내에 메도이드를 계산할 수 있는 많은 접근법이 있다.

포인트가 실제 라인에 있을 경우, Medoid 계산은 Hoare의 Quick-select 알고리즘에 ${\textstyle O(n)}$ O ${\textstyle O(n)}$ ) ${\textstyle O(n)}$ 에서 수행될 수 있는 중앙값 계산으로 감소한다.^[5]단, 고차원 실공간에서는 선형시간 알고리즘을 알 수 없다.랜드(LAND^[6])는 다른 점의 무작위 부분집합을 표본으로 추출하여 다른 점들에 대한 각 점의 평균 거리를 추정하는 알고리즘이다.It takes a total of ${\textstyle O\left({\frac {n\log n}{\epsilon ^{2}}}\right)}$ distance computations to approximate the medoid within a factor of ${\textstyle (1+\epsilon \Delta )}$ with high probability, where ${\textstyle \Delta }$ is the maximum distance between two points in앙상블Land는 근사 알고리즘이며, 더욱이 ${\textstyle \Delta }$ ${\textstyle \Delta }$ 은(는) apriori를 알 수 없을 수 있다 ${\textstyle \Delta }$ .

랜드는 토프랭크에 의해 활용되었는데, 토프랭크는 후보 점의 작은 부분 집합에 초점을 맞추고, 이 점들의 평균 거리를 정확히 평가하고, 최소값을 선택하기 위해 랜드가 획득한 추정치를 이용한다.TOPRANK은 평균 거리의 분포 가정 하에서 높은 확률의 정확한 중형( $O$ ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ $){\frac{5}{3}}\log ^{\frac {4}{3}n)}$ 의 ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ 거리 연산이 필요하다.

트림이 O ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ ( ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ $))$ $textstyle O(n^{\frac {3}{2}}^{\\)$ 가 있는 medoid를 찾는 알고리즘을 제시한다.점들에 대한 분포 가정 하에서 $세타 (d)}}$ 의 거리 ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ 평가.알고리즘은 삼각형 불평등을 이용해 검색 공간을 줄인다.

Meddit은^[4] 다중 무장 도적과의 중합체 연산 연결을 활용하고 상위 신뢰 바인딩 유형의 알고리즘을 사용하여 포인트에 대한 통계적 가정 하에 ${\textstyle O(n\log n)}$ ${\textstyle O(n\log n)}$ $){\textstyle O(n\log n)}$ 거리 ${\textstyle O(n\log n)}$ 평가를 받는 알고리즘을 얻는다.

또한 상관된 순차적 홀딩은^[8] 다중 무장 도적 기법을 활용하여 메딧을 개선한다.문제의 상관 구조를 활용함으로써 알고리즘은 필요한 거리 계산 횟수와 벽시계 시간 모두에서 급격한 개선(보통 1-2배 정도)을 산출할 수 있다.

구현

랜드, 토프랭크의 구현 및 트리밍은 여기에서 확인할 수 있다.Meddit의 구현은 이곳과 이곳에서 찾을 수 있다.상관된 순차적 절반의 구현은 여기에서 확인할 수 있다.

참고 항목

참조

^ Struyf, Anja; Hubert, Mia; Rousseeuw, Peter (1997). "Clustering in an Object-Oriented Environment". Journal of Statistical Software. 1 (4): 1–30.
^ van der Laan, Mark J.; Pollard, Katherine S.; Bryan, Jennifer (2003). "A New Partitioning Around Medoids Algorithm". Journal of Statistical Computation and Simulation. Taylor & Francis Group. 73 (8): 575–584. doi:10.1080/0094965031000136012. S2CID 17437463.
^ ^a ^b 뉴링, 제임스 & 플뢰레, 프랑수아(2016년); PMLR 54:185-193, 2017 온라인 이용 가능.
^ ^a ^b 바가리아, 비벡, 카맛, 고빈다 M, 은트라노스, 바실리스, 장, 마틴 J; & Tse, 데이비드 N.(2017), "다중무장 도적단을 통한 거의 선형적인 시간의 메도이드", Arxiv 프리프린트 온라인 이용 가능.
^ Hoare, Charles Antony Richard(1961); ACM 통신의 "알고리즘 65: find", 4(7), 321-322
^ Eppstein, David; & Wang, Joseph(2006); 그래프 알고리즘 및 적용에서 "중심성의 빠른 근사치" 5, 페이지 39-45
^ 오카모토, 카즈야; 첸, 웨이; & 리, 샹양(2008); 프랑코 P의 "대규모 소셜 네트워크를 위한 친밀도 중심성 순위";우, 샤오동; 인, 젠핑(eds). 알고리즘 워크샵 2008의 프런티어, 컴퓨터 과학의 강의 노트, 5059
^ Baharav, Tavor Z.; & Tse, David N. (2019); 신경 정보 처리 시스템의 진전에 관한 "상관 관련 순차적 분산을 통한 초고속 메도이드 식별".

[Struyf1997-1] Struyf, Anja; Hubert, Mia; Rousseeuw, Peter (1997). "Clustering in an Object-Oriented Environment". Journal of Statistical Software. 1 (4): 1–30.

[newpam-2] van der Laan, Mark J.; Pollard, Katherine S.; Bryan, Jennifer (2003). "A New Partitioning Around Medoids Algorithm". Journal of Statistical Computation and Simulation. Taylor & Francis Group. 73 (8): 575–584. doi:10.1080/0094965031000136012. S2CID 17437463.

[:1-3] 뉴링, 제임스 & 플뢰레, 프랑수아(2016년); PMLR 54:185-193, 2017 온라인 이용 가능.

[:0-4] 바가리아, 비벡, 카맛, 고빈다 M, 은트라노스, 바실리스, 장, 마틴 J; & Tse, 데이비드 N.(2017), "다중무장 도적단을 통한 거의 선형적인 시간의 메도이드", Arxiv 프리프린트 온라인 이용 가능.

[5] Hoare, Charles Antony Richard(1961); ACM 통신의 "알고리즘 65: find", 4(7), 321-322

[6] Eppstein, David; & Wang, Joseph(2006); 그래프 알고리즘 및 적용에서 "중심성의 빠른 근사치" 5, 페이지 39-45

[7] 오카모토, 카즈야; 첸, 웨이; & 리, 샹양(2008); 프랑코 P의 "대규모 소셜 네트워크를 위한 친밀도 중심성 순위";우, 샤오동; 인, 젠핑(eds). 알고리즘 워크샵 2008의 프런티어, 컴퓨터 과학의 강의 노트, 5059

[:corrSH-8] Baharav, Tavor Z.; & Tse, David N. (2019); 신경 정보 처리 시스템의 진전에 관한 "상관 관련 순차적 분산을 통한 초고속 메도이드 식별".

[1]

[2]

[3]

[4]

[5]

[6]

[8]

Search

메도이드

네임스페이스

더

목차

정의

메도이드 계산 알고리즘

구현

참고 항목

참조