의미없는 "Nearest Neighbor"에 대한 데이터 집합?

Question

"When Is 'Nearest Neighbor' Meaningful?"의 논문에서 우리는 "데이터와 쿼리 분포 또는 작업 부하와 관련하여 특정 조건 하에서 차원이 증가함에 따라 가장 인접한 까지의 거리가 가장 먼 거리에 접근한다는 것을 보여줍니다 다른 데이터 점에 대한 거리의 대비가 존재하지 않게됩니다. 우리가 확인한 조건 은 다른 작업이 가정하고있는 독립적이고 동일하게 분산 된 (IID) 차원 가정보다 훨씬 광범위합니다. "

제 질문은 어떻게이 효과와 유사한 데이터 집합을 생성해야합니까? 각 차원마다 0-255 범위의 난수를 사용하여 1000 개의 차원이있는 3 개의 점을 만들었지 만 점은 다른 거리를 만들고 위에서 언급 한 내용을 재현하지 않습니다. 변화하는 크기 (예 : 10 또는 100 또는 1000 차원)와 범위 (예 : [0,1])가 아무 것도 변경하지 않는 것 같습니다. 나는 여전히 다른 거리를 얻는다. 클러스터링 알고리즘!

Answer 1

나는 종이가 옳다고 생각한다. 첫째, 시험 : 시험에서 한 가지 문제는 너무 적은 점수를 사용하고있는 것일 수 있습니다. 나는 10000 포인트를 사용했고 내 결과는 (모든 차원에서 [0.0 ... 1.0]의 균등하게 분산 된 포인트입니다). DIM = 2의 경우, min/max는 거의 1000의 계수로 다르며 DIM = 1000의 경우에는 DIM = 10000의 계수가 1.248에 불과합니다. 그래서 나는이 결과가 종이의 가설을 확인했다고 말하고 싶습니다. 세 무작위로 생성 된 벡터, A, B 및 C의 총 거리가 이러한 벡터들의 각 행의 거리의 합에 기반을하자 :

DIM/N = 2/10000 
min/avg/max= 1.0150906548224441E-5/0.019347838262624064/0.9993862941797146  
DIM/N = 10/10000.0 
min/avg/max= 0.011363500131326938/0.9806472676701363/1.628460468042207 
DIM/N = 100/10000 
min/avg/max= 0.7701271349716637/1.3380320375218808/2.1878136533925328 
DIM/N = 1000/10000 
min/avg/max= 2.581913326565635/3.2871335447262178/4.177669393187736 
DIM/N = 10000/10000 
min/avg/max= 8.704666143050158/9.70540814778645/10.85760200249862 

DIM/N = 100000/1000 (N=1000!) 
min/avg/max= 30.448610133282717/31.14936583713578/31.99082677476165 

난 설명은 다음과 같다. 벡터의 치수가 커질수록 차이의 총합이 일반적인 평균에 가까워집니다. 즉, 벡터 C가 모든 요소에서 다른 벡터 B가 A보다 큰 거리를 가질 가능성은 거의 없습니다. 치수가 커지면 C와 B는 A와 (그리고 서로) 거리가 점점 멀어집니다.

내 테스트 데이터 세트는 다음과 같이 작성되었습니다. 데이터 세트는 본질적으로 0.0에서 1까지의 큐브입니다.모든 차원에서 0. 좌표는 0.0과 1.0 사이의 모든 차원에서 균일 한 분포로 작성되었습니다. 실시 예 번호 (N = 10,000, DIM = 2..10000]) : 허용 대답 here의 하단에 주어진 다음 식

public double[] generate(int N, int DIM) { 
    double[] data = new double[N*DIM]; 
    for (int i = 0; i < N; i++) { 
     int pos = DIM*i; 
     for (int d = 0; d < DIM; d++) { 
      data[pos+d] = R.nextDouble(); 
     } 
    } 
    return data; 
} 

우리 얻을 :

D = 2 -> 98,460

D = 10 -> 142.3

D = 100 -> 1.84

D = 1,000 -> 0.618

D = 10,000 -> 0.247

D = 10 -> 0.0506 (N = 1000 사용)

I는 통계 부 [참조] (또한,이 질문을

Answer 2

전에도 들어 본 적이 없었으므로, 나는 have seen that real and synthetic datasets in high dimensions이 실제로 문제의 논문에 대한 주장을 뒷받침하지 않기 때문에 거의 방어 적이 지 않습니다.

결과적으로 첫 번째로 더럽고 서투른 어쩌면 좋지 않은 첫 번째 시도는 원하는 차원으로 구를 생성 한 다음 (I do it like like this) 중심에 쿼리를 배치하는 것입니다. 구.

이 경우 모든 포인트는 쿼리 포인트와 동일한 거리에 있으므로 가장 가까운 이웃에 가장 가까운 이웃 거리가 있습니다.

이것은 물론 치수와는 관련이 없지만 종이의 그림을보고 생각한 것입니다. 그것은 당신을 응시하기에 충분해야하지만 확실하게 더 나은 데이터 세트가 생성 될 수 있습니다.

---

편집에 대한 각 지점에 대한

거리가 더 크기에 더 큰 있어요 !!!!

이것은 예상되는데, 차원 공간이 높을수록 공간이 더 좁아 지므로 거리가 더 넓어지기 때문입니다. 또한 예를 들어 유클리드 거리 (Euclidean distance)를 생각하면 차원이 커짐에 따라 더 강해집니다.