KD 트리 :`leafsize` 매개 변수의 의미
SciPy의 KD Tree 구현을보고 있습니다. 나는 leafsize매개 변수가 혼란 스럽습니다.
알고리즘이 무차별 대입으로 전환되는 지점 수입니다. 기본값 : 16.
이것이 BST의 잎 수입니까? 그렇다면 기본적으로 KD 트리에는 32 개 이하의 포인트가 포함됩니다. 이것은 특히 k = 2의 사용 사례에서 비합리적으로 작게 보입니다. 매개 변수를 잘못 해석하고 있습니까?
답변
매개 변수 leafsize는 트리의 최대 리프 수 (경계되지 않음)를 제어하지 않고 트리의 단일 리프와 관련된 입력 포인트 수를 제어합니다. 나무에 64 개의 포인트가 추가되는 것을 고려하십시오. 각 포인트가 단일 리프와 연결되면 7 레벨 깊이의 전체 트리를 얻을 수 있으며 포인트가 필요한 모든 처리는이 7 레벨을 내려서 찾을 수 있습니다. 또는 잎 크기가 16이면 깊이가 3 단계에 불과하고 나무의 각 잎이 16 점과 연관되는 나무를 얻게됩니다. 포인트를 처리하려면 트리의 3 개 레벨을 내림차순으로 내린 다음 리프의 16 개 포인트를 각각 테스트합니다 (순서가 없기 때문에). 이 값은 성능을 위해 조정할 수 있으며 경험적으로 최상의 값은 트리가 정확히 사용되는 방식에 따라 다릅니다.
개념적으로 다음은 서로 다른 leafsize값을 위해 구축되는 트리의 예입니다 .
scipy 소스 코드leafsize 에서 매개 변수가 트리 구축 프로세스를 어떻게 단락 하는지 확인할 수 있습니다 . 이것은 나무의 잎에서 사이 와 포인트를 정렬되지 않은 상태로 남깁니다 .leafsize/2leafsize