ELKI DBSCAN with R * -Tree

Question

ELKI 라이브러리를 사용하여 DBSCAN 클러스터링 테스트 응용 프로그램을 구현하려고합니다. 내 데이터 세트는 6 차원이며 약 100.000 개의 개체로 구성됩니다.

내 코드에서 R * -Tree ELKI 최적화를 사용하려고했지만 코드를 벤치마킹하면 여전히 O (n^2)와 함께 사용되는 것처럼 보입니다.

이

내가 내 응용 프로그램 내에서 사용하는 코드입니다 :

ListParameterization dbscanParams = new ListParameterization(); 
dbscanParams.addParameter(DBSCAN.Parameterizer.EPSILON_ID, eps); 
dbscanParams.addParameter(DBSCAN.Parameterizer.MINPTS_ID, minPts); 
dbscanParams.addParameter(DBSCAN.DISTANCE_FUNCTION_ID, EuclideanDistanceFunction.class); 

DBSCAN<DoubleVector, DoubleDistance> dbscan = ClassGenericsUtil.parameterizeOrAbort(DBSCAN.class, dbscanParams); 

ArrayAdapterDatabaseConnection arrayAdapterDatabaseConnection = new ArrayAdapterDatabaseConnection(featuresMatrix, featuresLabels); 

ListParameterization dbparams = new ListParameterization(); 
dbparams.addParameter(AbstractDatabase.Parameterizer.INDEX_ID, RStarTreeFactory.class); 
dbparams.addParameter(RStarTreeFactory.Parameterizer.BULK_SPLIT_ID, SortTileRecursiveBulkSplit.class); 
dbparams.addParameter(AbstractDatabase.Parameterizer.DATABASE_CONNECTION_ID, arrayAdapterDatabaseConnection); 
dbparams.addParameter(AbstractPageFileFactory.Parameterizer.PAGE_SIZE_ID, pageSize); 

Database db = ClassGenericsUtil.parameterizeOrAbort(StaticArrayDatabase.class, dbparams); 

db.initialize(); 

Clustering<Model> result = dbscan.run(db); 

위의 코드를 실행하면 이러한 결과에 이르게 :

| NUM_OBJECTS | TIME(ms) | 
|-------------|------------| 
| 4444  | 1508  | 
| 8887  | 5547  | 
| 17768  | 23401  | 
| 35536  | 103733 | 
| 71040  | 426494 | 
| 142080  | 1801652 | 

시간은 일반 간단한에 System.currentTimeMillis를 사용하여 벤치마킹() dbscan.run (db) 주변. times 칼럼을 보면 트렌드가 nlog (n)과 같지 않고 n^2와 비슷하지만 R * -Tree 최적화로 ELKI DBSCAN을 사용하기 위해 누락 된 부분을 이해할 수 없다는 것을 알 수 있습니다.

도움이나 제안을 해주셔서 감사합니다.

Answer 1

쿼리 반경 엡실론을 너무 크게 선택하면 모든 개체에 O(n) 개의 이웃이 생깁니다.

그러면 색인 지원이있는 경우에도 런타임은 O(n^2) 이상입니다. 각 쿼리의 응답 크기가 O(n)이기 때문입니다.

개체의 평균 10 %가 엡실론 반경 내에 있도록 엡실론을 선택한 경우 런타임은 O(n * 10% * n), 즉 O(n^2)이됩니다.

O(n log n)의 이론적 런타임이 실제로 런타임에 O(n log n)이되지 않을 수 있음을 보여줍니다. R * -tree는 평균으로 O(log n)의 반경 또는 kNN 쿼리에 응답 할 수 있습니다. 응답 세트 크기가 무시 될 수있는 작은 응답 세트의 경우. 보다 정확한 분석을 수행하면 실행 시간이 O(log n + |answer| log |answer|)으로 늘어날 수 있습니다 (현재 거리별로 답변을 정렬하기 때문에 일부 알고리즘에서는이를 제거 할 수 있습니다).

알고리즘은 O(n*n)으로 가정하면 모든 객체에 대해 다른 모든 객체를 거리별로 정렬하므로 O(n*n log n) 런타임이 필요합니다. 다행히 정렬은 잘 최적화되어 있으므로 log n은 중요하지 않습니다.