private Separation findSeparation ( Relation < NumberVector > relation , DBIDs currentids , int dimension , Random r ) { Separation separation = new Separation ( ) ; // determine the number of samples needed, to secure that with a specific // probability // in at least on sample every sampled point is from the same cluster. int samples = ( int ) Math . min ( LOG_NOT_FROM_ONE_CLUSTER_PROBABILITY / ( FastMath . log1p ( - FastMath . powFast ( samplingLevel , - dimension ) ) ) , ( double ) currentids . size ( ) ) ; // System.out.println("Number of samples: " + samples); int remaining_retries = 100 ; for ( int i = 1 ; i <= samples ; i ++ ) { DBIDs sample = DBIDUtil . randomSample ( currentids , dimension + 1 , r ) ; final DBIDIter iter = sample . iter ( ) ; // Use first as origin double [ ] originV = relation . get ( iter ) . toArray ( ) ; iter . advance ( ) ; // Build orthogonal basis from remainder double [ ] [ ] basis ; { List < double [ ] > vectors = new ArrayList <> ( sample . size ( ) - 1 ) ; for ( ; iter . valid ( ) ; iter . advance ( ) ) { double [ ] vec = relation . get ( iter ) . toArray ( ) ; vectors . add ( minusEquals ( vec , originV ) ) ; } // generate orthogonal basis basis = generateOrthonormalBasis ( vectors ) ; if ( basis == null ) { // new sample has to be taken. i -- ; if ( -- remaining_retries < 0 ) { throw new TooManyRetriesException ( "Too many retries in sampling, and always a linear dependant data set." ) ; } continue ; } } // Generate and fill a histogram. DoubleDynamicHistogram histogram = new DoubleDynamicHistogram ( BINS ) ; double w = 1.0 / currentids . size ( ) ; for ( DBIDIter iter2 = currentids . iter ( ) ; iter2 . valid ( ) ; iter2 . advance ( ) ) { // Skip sampled points if ( sample . contains ( iter2 ) ) { continue ; } double [ ] vec = minusEquals ( relation . get ( iter2 ) . toArray ( ) , originV ) ; final double distance = deviation ( vec , basis ) ; histogram . increment ( distance , w ) ; } double [ ] th = findAndEvaluateThreshold ( histogram ) ; // evaluate threshold if ( th [ 1 ] > separation . goodness ) { separation . goodness = th [ 1 ] ; separation . threshold = th [ 0 ] ; separation . originV = originV ; separation . basis = basis ; } } return separation ; }
This method samples a number of linear manifolds an tries to determine which the one with the best cluster is .