- Timestamp:
- 04/12/17 12:15:37 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/VantagePointTree.cs
r14787 r14855 84 84 public void Search(T target, int k, out IList<T> results, out IList<double> distances) { 85 85 var heap = new PriorityQueue<double, IndexedItem<double>>(double.MaxValue, double.MinValue, k); 86 Search(root, target, k, heap, double.MaxValue); 86 double tau = double.MaxValue; 87 Search(root, target, k, heap, ref tau); 87 88 var res = new List<T>(); 88 89 var dist = new List<double>(); 89 90 while (heap.Size > 0) { 90 res.Add(items[heap.PeekMinValue().Index]); 91 res.Add(items[heap.PeekMinValue().Index]); // actually max distance 91 92 dist.Add(heap.PeekMinValue().Value); 92 93 heap.RemoveMin(); 93 94 } 94 res.Reverse(); 95 res.Reverse(); 95 96 dist.Reverse(); 96 97 results = res; … … 98 99 } 99 100 100 private void Search(Node node, T target, int k, PriorityQueue<double, IndexedItem<double>> heap, double tau = double.MaxValue) {101 private void Search(Node node, T target, int k, PriorityQueue<double, IndexedItem<double>> heap, ref double tau) { 101 102 if (node == null) return; 102 103 var dist = distance.Get(items[node.index], target); 103 104 if (dist < tau) { 104 if (heap.Size == k) heap.RemoveMin(); 105 heap.Insert(-dist, new IndexedItem<double>(node.index, dist)); //TODO check if minheap or maxheap should be used here105 if (heap.Size == k) heap.RemoveMin(); // remove furthest node from result list (if we already have k results) 106 heap.Insert(-dist, new IndexedItem<double>(node.index, dist)); 106 107 if (heap.Size == k) tau = heap.PeekMinValue().Value; 107 108 } … … 109 110 110 111 if (dist < node.threshold) { 111 if (dist - tau <= node.threshold) Search(node.left, target, k, heap, tau); // if there can still be neighbors inside the ball, recursively search left child first112 if (dist + tau >= node.threshold) Search(node.right, target, k, heap, tau); // if there can still be neighbors outside the ball, recursively search right child112 if (dist - tau <= node.threshold) Search(node.left, target, k, heap, ref tau); // if there can still be neighbors inside the ball, recursively search left child first 113 if (dist + tau >= node.threshold) Search(node.right, target, k, heap, ref tau); // if there can still be neighbors outside the ball, recursively search right child 113 114 } else { 114 if (dist + tau >= node.threshold) Search(node.right, target, k, heap, tau); // if there can still be neighbors outside the ball, recursively search right child first115 if (dist - tau <= node.threshold) Search(node.left, target, k, heap, tau); // if there can still be neighbors inside the ball, recursively search left child115 if (dist + tau >= node.threshold) Search(node.right, target, k, heap, ref tau); // if there can still be neighbors outside the ball, recursively search right child first 116 if (dist - tau <= node.threshold) Search(node.left, target, k, heap, ref tau); // if there can still be neighbors inside the ball, recursively search left child 116 117 } 117 118 } … … 124 125 var node = new Node { index = lower }; 125 126 var r = new MersenneTwister(); //outer behaviour does not change with the random seed => no need to take the IRandom from the algorithm 126 if (upper - lower <= 1) return node; // if we did not arrive at leaf yet127 if (upper - lower <= 1) return node; 127 128 129 // if we did not arrive at leaf yet 128 130 // Choose an arbitrary point and move it to the start 129 var i = (int)(r.NextDouble() / 1* (upper - lower - 1)) + lower;131 var i = (int)(r.NextDouble() * (upper - lower - 1)) + lower; 130 132 items.Swap(lower, i); 131 133
Note: See TracChangeset
for help on using the changeset viewer.