Machine learning approximation techniques using dual trees

Master in Artificial Intelligence (UPC-UB-URV) Master of Science Thesis Machine Learning Approximation Techniques Using Dual Trees Denis Ergashbaev Supervisor: Oriol Pujol Vila Dept. Matemtica Aplicada i Anlisi, University of Barcelona (UB) April 2015 ABSTRACT This master thesis explores a dual-tree framework with underlying kd-tree space partitioning data structure as applied to a particular class of machine learning problems that are collectively referred to as generalized n-body problems. We propose a novel algorithm based on the dual-tree framework to accelerate the task of discovering characterizing boundary points (CBP) – a set of data points defined by geometry rules and representing an optimal robust interclass boundary. Designed with support for both approximate and exact computations, experimental results confirm superior runtime properties of the algorithm compared to a state-of-the-art solution. Furthermore, we propose an improvement of the Boosted Geometry-Based Ensembles algorithm that constructs a CBP-based strong classifier. Owning to our modification of the original learner, the scalability of the algorithm is improved to be able to operate on the datasets of higher size and dimensions while improving speed and maintaining high accuracy of classification. 3 ACKNOWLEDGEMENTS This work would not have been possible without the firm support of my final thesis supervisor Oriol Pujol. I am deeply indebted to him for his encouragement, guidance, and mentorship. I am thankful to my family for their support of my delayed endeavor of pursuing a master’s degree. They have both pushed me forward and held me from behind when I was about to give up. Being so remote in distance, my American family has stayed close to me over the years. I miss you so much! My cool boss Thomas for letting me go and keeping me at the same time. It helped a lot. To the PD department – Oliver, Gordon, Stefan, Steffen, and Martin – for fixing my bugs and covering up for me. Thanks. “Katta rahmat” to my friend Sarvar for endless discussions about academic life and computer science, our shared adventures in Barcelona, and his critical role in making me commit to this master’s program. I am grateful and obliged to Dilshod Ibragimov who always supports my various aspirations, including this master’s program, and helps me to keep on growing. Thank you. Thanks goes to my long-time flatmates – Lorenzo and Hadi – for friendship, many fun parties, adventures, and incessant tea talks. This is not to forget El Arbi and Pablo, my first ones, living with you was so much enjoyable and helped me to get on terms with living in the big city again. Pablo, Jeroni, Lorenzo, and Iosu, our sleepless all-nighters, crunching the brutal assignments and coffees in the morning helped me survive the first semester. Being able to rely on you in a foreign country made my stay so much more enjoyable. Pablo, for introducing me to the Spanish legal system. Dear members of the machine learning beers community – Anna, Alex, Eloi, Carles and Oriol – for beers and geeky talks. Carles and Alex, for setting up Elbereth and letting me run my experiments there. “Cheers!” 5 The classes of Javier Larrosa and Albert Oliveras were amazingly good, useful, and involving. I learned so much. My Russian/Ukranian friends – Oleg, Pavel, Grigoriy, Aleksandr, Igor – made my stay in Spain to feel more like at home, while the great Spanish class team – Xavier, Maria, Vladimir, Svetlana, Arancha & Ainhoa made learning Spanish so fun. Simran, for her birthday cake and good times. I know I have missed many more people without whom the whole master’s would not be possible or at least much less enjoyable: “muchas gracias”. 6 CONTENTS 1 introduction 17 1.1Motivation.......................... 17 1.2Objectives .......................... 17 1.3Contributions of the Research . . . . . . . . . . . . . . . 18 1.4Organization......................... 18 2 background and state of the art 21 2.1Kd-trees ........................... 21 2.2Nearest-neighbor Search . . . . . . . . . . . . . . . . . . 24 2.3DualTrees .......................... 25 2.4Geometry-Based Ensembles . . . . . . . . . . . . . . . . 29 3 proposal 35 3.1Faster CBP Computations . . . . . . . . . . . . . . . . . 35 3.1.1Dual-Tree Architecture . . . . . . . . . . . . . . . 38 3.1.2PruningRules.................... 38 3.1.3Exact CBP Computation . . . . . . . . . . . . . . 38 3.1.4Approximate CBP Computation . . . . . . . . . 41 3.1.5Finding Reference Point k............. 44 3.1.6LocalSearch..................... 46 3.2A CBP-Based Classifier . . . . . . . . . . . . . . . . . . . 48 4 experiments and results 51 4.1Understanding the Model . . . . . . . . . . . . . . . . . 51 4.1.1Effect of Leaf Size . . . . . . . . . . . . . . . . . . 52 4.1.2Effect of Dimensionality . . . . . . . . . . . . . . 56 4.1.3Effect of Local Search . . . . . . . . . . . . . . . 57 4.1.4Curse Of Dimensionality . . . . . . . . . . . . . 60 4.1.5A CBP-Based Classifier . . . . . . . . . . . . . . 61 4.2Results ............................ 63 4.2.1CBPComputation ................. 63 4.2.2A CBP-Based Classifier . . . . . . . . . . . . . . 65 5 conclusions and future work 69 a detailed results 75 7 LIST OF FIGURES Figure 1A3-dimensional kd-tree . . . . . . . . . . . . . 23 Figure 2Splittingrules ................... 23 Figure 3Single-tree vs dual-tree traversal . . . . . . . . 26 Figure 4CBP decision boundaries and areas of influence 30 Figure 5Illustration of the characteristic boundary point definition...................... 30 Figure 6Gabrielgraph ................... 31 Figure 7Nearest neighbor graph . . . . . . . . . . . . . 31 Figure 8banana (1192x2). Representation of the reduced bananadataset. .................. 36 Figure 9Dual-tree architecture: one tree . . . . . . . . . 38 Figure 10 Dual-tree architechture: two trees . . . . . . . . 38 Figure 11 Pruningrule.................... 40 Figure 12 Tighter pruning rule . . . . . . . . . . . . . . . 40 Figure 13 Worstcase ..................... 41 Figure 14 Strict pruning in 3D................ 41 Figure 15 Relaxed pruning rule: minimum distance to point ........................ 43 Figure 16 Relaxed pruning rule: nonadjacent hyperrectangles........................ 43 Figure 17 Bounding hyperrectangle . . . . . . . . . . . . 45 Figure 18 Tight hyperrectangle . . . . . . . . . . . . . . . 45 Figure 19 LocalSearch.................... 47 Figure 20 Overly restrictive spheric boundary . . . . . . 47 Figure 21 Boosted OGE: filtered merge . . . . . . . . . . 49 Figure 22 Boosted OGE: cascade . . . . . . . . . . . . . . 49 Figure 23 EEGEye (7200x2): Leaf size growth . . . . . . . 52 Figure 24 EEGEye (7200x4): Leaf size growth . . . . . . . 53 Figure 25 EEGEye (7200x2): Break-down of dual-tree algorithm (conservative pruning) time consumption.......................... 53 Figure 26 EEGEye (7200x4): Break-down of dual-tree algorithm (conservative pruning) time consumption.......................... 54 Figure 27 EEGEye (7400x2). Worst case vs real computations in relation to the leaf size . . . . . . . . . 55 Figure 28 EEGEye (7400x4). Worst case vs real computations in relation to the leaf size . . . . . . . . . 55 Figure 29 Absolute time performance of Sokal and Dual- Tree algorithms as dataset dimensionality increases........................ 56 9 1 INTRODUCTION 1.1 motivation Many of the machine learning methods – including all-nearest- neighbors problem, range search, kernel density estimation, and two-point correlation – are naively quadratic in the number of data points [11]. This time complexity compromises their use in the large-scale machine learning applications thus demanding more efficient solutions to accelerate the naive approaches. One commonly used method to reduce the time complexity of solving these problems is application of space-partitioning data structures, such as kd-trees, and use of branch-and-bound algorithms to improve the runtime speed [7]. This idea has been further developed for a subset of the problems falling in the class of generalized n-body problems by applying a dual-tree framework. Initially introduced by Alexander Grey [12], the dual-tree framework has been claimed and theoretically proven to achieve a nearlinear performance for a range of n-body problems. Nevertheless, beyond a narrow circle of researchers, the dual-tree approach has not yet been adopted in broader scientific community. With relative scarce coverage which is limited by a few papers and presentations, we believe that dual trees deserve a more exploration. 1.2 objectives This thesis sets forward several objectives: 1. To implement a dual-tree framework based on the general algorithm provided in [7,12] and to apply it to one of the machine learning problems that would benefit from complexity reduction. 2. To explore the behavior of the proposed algorithm on the datasets of different size and dimensionality comparing the performance with a state-of-the-art solution. 17 introduction 3. To provide an approximate solution based on dual trees as an acceptable trade-off between computational complexity of the algorithm and accuracy of the results. 1.3 contributions of the research This work makes several contributions: 1. It provides a workable reference implementation of the dualtree framework based on the kd-tree data structure and written in python programming language. 2. The reference implementation of the dual tree framework is applied to one of the machine learning problems: finding characterizing boundary points [24,23]. Possible dual-tree architectures as well as relevant pruning and local search strategies are compared. 3. The performance of the devised framework is verified against datasets of different size and dimensionality, reporting the gains in speed, worst and real cases of required computations. 4. Along with the exact solution an approximate technique to find characterizing boundary points is developed and applied to the Boosted OGE problem [23] in order to achieve computational tractability for datasets of bigger size and higher dimensions. 1.4 organization This report takes off with the review of kd-tree (Section 2.1), a spacepartitioning data structure, and moves on to introduce a dual-tree framework (Section 2.3) that integrates kd-trees into a new higherorder divide-and-conquer algorithm to solve generalized n-body problems. A description of the Geometry-Based Ensembles, a new classifier based on the characterizing boundary points (CBP), ensues in Section 2.4. Following review of the state-of-the-art in Section 3.1we formulate a proposal for a novel algorithm to construct CBPs that applies the dual-tree framework with custom developed pruning strategies and a local search in order to gain speed improvements over the state- of-the art technique. Subsequently, in Section 3.2, we propose two alternative models to the Boosted OGE classifier (that uses CBPs as its building blocks) that significantly improve its time performance on larger datasets. Peculiarities of the new algorithm for CBP computation and proposed Boosted OGE models are analyzed in Section 4.1, while the 18 1.4 organization summary of the experimental results is provided in Section 4.2. Lastly, in Chapter 5we conclude the report with the short summary of the scope of work conducted and the new areas of research that this master thesis has opened. 19 2 BACKGROUND AND STATE OF THE ART The following sections will present a common space partitioning data structure called kd-tree enabling execution of fast data queries. It is then followed by discussion of the dual-tree approach that builds on top of kd-trees to provide an efficient algorithm for a range of n-body problems. The section concludes with an overview of the promising geometry-based ensemble technique used for classification tasks. 2.1 kd-trees Kd-tree (short for k-dimensional tree) is a space-partitioning data structure, which can be viewed as special case of the binary space partitioning tree. It was invented by J.L. Bentley [1] to provide support for efficient range and nearest neighbor searches in multidimensional spaces. Generalizing the binary search tree from one to higher dimensions, the kd-trees recursively partition space into half-spaces at each level of the tree. Each node in a kd-tree represents a hyperrectangle whose faces are aligned with the axes of coordinates. Algorithm 1lists the main steps involved in the construction of the kd-tree. Given a set Sof data points in space Rdthe algorithm proceeds to recursively bisect the space into adjacent cells. Partitioning of a relevant branch stops once the cell defined by the bounding hyperrectangle contains at most a given number of data points. Figure 1is a visual representation of the resulting space partitioning when applied to a three-dimensional data set. The root cell is bisected with a red hyperplane into two halfspaces, which are then recursively split by other hyperplanes (marked with green and blue colors). There are two important considerations that need to be taken into account when constructing a kd-tree: Leaf size. The algorithm stops dividing the space as soon as the current node has at most the amount of data points specified by this 21 background and state of the art Algorithm 1:Kd −tree. Kd-tree construction Input: Set of data points ={xi},xi∈Rd, depth Output: kd-tree begin axis :=select axis() splitting point :=by axis from data points // create node and subnodes node :=new node() node.split =splitting point new depth :=depth +1 node.le f t child :=kdtree(points ∈data points ≤ splitting point,new depth) node.right child :=kdtree(points ∈data points > splitting point,new depth) end parameter. While a too low value for the leaf (or bucket) size would increase overhead of traversing the nodes [22], letting this value approach the size of the dataset makes queries become a brute force computation. As it will be demonstrated later, in the context of the dual-tree framework, the leaf size will have a direct impact on the ability to perform efficient pruning. Splitting rules. The exact structure of the tree and associated spacial subdivision depends on the procedure called splitting rule which selects a splitting hyperplane at each recursive step [17]. Standard split. The original paper on kd-trees has proposed to determine the axis to split on by the formula D=L mod k +1; Dis the axis to be chosen for the node at level Lfor the dataset dimensionality k[1,9], whereas the partition point at the established dimension is chosen to be a random value. If, for instance, we have a two dimensional dataset, then the algorithm will split on the xdimension at the first level, on yat the second level, and then on xagain. The splitting stops when the value of points held by each leaf is reached. A further extension of the standard splitting rule is to split on the median value of the selected axis [2] in order to achieve a balanced kd-tree where each node is equally distanced from the root. Midpoint split. The splitting hyperplane bisects the longest side of the cell. In contrast to the standard splitting rule, the spread measure has no importance in that case. 22 2.1 kd-trees Figure 1.: A 3-dimensional kd-tree [3] Sliding-midpoint. This rule is a combination of the previous two strategies, where first a provisional split is made along the longest side of the cell. In case that all the points appear only on one side of the hyperplane, the splitting hyperplane is moved along the axis to capture some of them. The result of application of this rule is that the cells satisfy a packing constraint, that bounds the number of disjoint cells of a given size that can overlap a ball of certain radius [17]. Figure 2compares the effect of using the three splitting rules in the kd-trees. In this work, the kd-trees were built using the slidingmidpoint rule for the reasons that will become obvious later on. Figure 2.: Splitting rules [17] 23 background and state of the art 2.2 nearest-neighbor search As has been mentioned, one of the primary applications of the kdtrees is nearest-neighbor search. Given a query dataset XQcontaining NQpoints and a point xrfrom a reference dataset XRof size NR, the nearest neighbor algorithm is defined as follows (a most commonly used euclidean distance is assumed): Compute NN (xq) = arg min ||xq−xr|| (1) The most straightforward solution for the problem – a linear search has a running time of O(dN), where dis a dimensionality of the metric space. Meantime, it has been shown that one of the two primary applications of the kd-trees – finding a nearest point – has O(log N)complexity given random distributed points [9]. Algorithm 2provides a highly abstract perspective of nearest neighbor queries with kd-trees. It is implemented as a 2-way recursion where first the root node of the kd-tree is queried for the point xq. To find the exact nearest neighbor it proceeds to traverse through its child nodes provided that the distance of the nearest neighbor found so far to the query point xqis larger then the distance of the current node to the query point. Algorithm 2:NN. Nearest-neighbor search Input: query point xq, node root node on first entry, dinitial distance set to ∞on entry, xbest best candidate found so far, dbest corresponding best distance Output:xbest,dbest begin if d>dbest then // disregard (prune) the node return end if is lea f node(node)then [xbest,dbest] = NNBase(xq,node,dbest) else [nodecloser,dcloser,nodef urther,df urther] = order by dist(xq,node.le f t child,node.right child) NN(xq,nodecloser,dcloser,xbest,dbest) NN(xq,nodef urther,df urther,xbest,dbest) end end 24 2.3 dual trees 2.3 dual trees There is a class of problems in machine learning, such as all-nearest- neighbors, kernel density estimation, n-point correlation that require comparison of each pair of points individually in order to provide a solution. This class of problems was described by Alexander G. Gray in his Ph.D. dissertation and was given a name generalized N-body problems [12]. The particularity of these problems is that it is generally not possible to determine the relationships between individual pairs of points analytically without considering each pair of the points individually [12]. Thus, the straightforward solution dictates an O(N2)time complexity. However, several approaches in computational geometry achieve an O(N log N)runtime performance [12]. Consider for instance the nearest neighbor problem described in Equation (1). A related ‘N- body problem’ would be finding all nearest neighbors: ∀xq,Compute NN(xq) = arg min ||xq−xr|| (2) Using kd-trees as a supporting structure for the task will reduce the computation cost from O(N2)to O(N log N)[12]. The assumptions in that case is that NR=NQ=Nand we can ignore the cost of constructing a kd-tree as it will be amortized over time. However, even this cost is prohibitive for the massive datasets in machine learning. In his Ph.D. thesis and subsequent publications A. Grey devises a dual-tree framework that builds on top of the existing space partitioning data structures, such as kd-trees but also ball trees, and applies divide-and-conquer algorithmic strategy to bring forward a O(N)expected runtime algorithm [12]. It exploits the characteristic of N-body problems that each data point in the reference dataset NRhas to be compared with all of the data points from the query dataset QRand introduces pruning rules to be able to reduce the required number of operations. Instead of using a single space-partitioning data structure, the algorithm utilizes two trees and extends a single tree traversal to a dual tree traversal. It needs to be mentioned, that oftentimes, the reference and query datasets are the same (NR=NQ). The dual tree framework is best exemplified on the all-nearest neighbor search. The fundamental idea is to process the points in chunks instead of making individual queries for each point xq. As the space-partitioning data structures group similar points together, work of finding nearest 25 background and state of the art However, we could derive a better algorithm based on the formula that Matula and Sokal provide to define the Gabriel graph edges [18]. d(i,j)2<d(i,k)2+d(j,k)2∀i,j,k∈M,i6=j6=k(7) Accordingly, iand jform a valid edge of the Gabriel graph, if the squared distance d(i,j)2is smaller than the sum of the squared distances of iand jto any other point in the dataset. Adopting this formula to the task of locating CBPs, we obtain a faster Algorithm 4. In contrast to the naive brute-force approach it exhibits a lower complexity of O(M3+dM2)as no explicit computation of provisional CBPs is required any longer. Algorithm 4:Sokal. Sokal algorithm for CBP construction Input: Set of data points S={xi,yi} ∈ Rdbelonging to class yi∈ {+1, −1} Output: Set of tuples of indexes {(i,j)}that identify the generating data points of CBP Compute squared Euclidean distance d(i,j)2from each point xito xjin M Initialize the set of indexes that define the CBP, E={} begin foreach xi|yi= +1do foreach xj|yj=−1do foreach xk|yk= +1or yk=−1do cbp found = true; if xi6=xkand xj6=xkthen if d(i,j)2≥d(i,k)2+d(j,k)2then cbp found = false; break; end end end if cbp f ound then E=E∪{(xi,xj)} end end end end boosted oge. Boosted Geometry-Based Ensembles [23] is a result of applying gradient boosting to the original Geometry-Based Ensembles (GE) framework [24] in order to achieve controlled complexity of the model. 32 2.4 geometry-based ensembles GE constructs an additive model based on the linear combination of classifiers. Based on the obtained CBPs, a set of base linear classifiers is constructed in the following way [23]: πxi,j cp (x) = (x−xi,j cp)~ nxi,j cp ~ nxi,j cp =xi−xj kxi−xjk(8) Having obtained the classifiers, the ensemble is created via an additive model F: F(x) = N ∑ k=1 ρkhk(x) = N ∑ k=1 ρksign(πk(x)) where Nis the number of CBPs and ρis a weighting vector (9) The simplest approach to gradient boosting uses L2-penalized least squares incremental residual minimization as described in Algorithm 5. Algorithm 5:BoostedOGE. L2-penalized least squares GE boost begin A(k,i) = sign(πk(xi)) k∈ {1...N},i∈ {1...M}; F0(x) = y; for t = 1to T do ˆ y=yi−Ft−1(xi)i=1, M; ρ=ˆ yTA M+λ; at=arg mina∑M i=1(ˆ yi−ρah(xi;a))2; Ft(x) = Ft−1(x) + ρth(x;at); end end According to the experimental results [23] the regularized versions of Boosted OGE with L2-penalization performed on par with the reference classifiers SVM and OGE, while outperforming Adaboost with decision stumps. Boosted OGE has a nice property that creation of the set of classifiers (predefined by CBPs) and the incremental optimizations are decoupled. This makes the algorithm useful for online and parallel extensions [23]. Nevertheless, Boosted OGE has clear inferior performance to the reference classifiers on some of the datasets. The author contemplates, that it could be caused by the limited space of base classifiers in the selection process. Being a subset of Gabriel graph, the number of CBPs is limited by the same strict geometric rules narrowing the space of potential classifiers. A relaxation of the CBP definition that 33 background and state of the art would allow kpoints to intrude the hypersphere is recommended as a potential strategy to expand the space of classifiers. 34 3 PROPOSAL This master thesis proposes a novel application of a dual-tree framework to a task of computing characteristic boundary points. Due to the inherent O(N3)computational complexity of the state-of-the-art Sokal algorithm the objective of devising a faster solution gains importance for medium and large sized datasets. 3.1 faster cbp computations Let us define the reference dataset XRas data points belonging to class −1 and the query dataset XQas the points of class +1. While the task of computing CBPs is not strictly an n-body problem, it does share one characteristic common to this class of problems: in the worst case deriving a solution requires comparison of each data point in the reference set XRto each data point in the query set QR. Furthermore, according to the Equation 7, we also need to compare the distances between the pairs of XRand XQto the points XR∪XQin order to verify validity of a CBP. weaknesses of sokal algorithm Consider for instance a reduced banana dataset plotted in Figure 8. The Sokal algorithm is largely oblivious to the spatial location of the data points: 1. Even if there are interfering points between xiand xjthat clearly break their generating ability, the algorithm will still perform the comparison. 2. When comparing the distance between xiand xjto the rest of the dataset XR∪XQ, no heuristics is applied to ensure that the point most capable of breaking the CBP tie are considered first. The algorithm iterates sequentially through the elements of XR∪XQ. dual-tree algorithm to find cbps Observing this relationship, it is reasonable to argue that bringing space-awareness to the algorithm would make it more efficient by reducing excessive computations. While we could start designing a point-to-point algorithm based on a single kd-tree, our awareness that the task of computing 35 proposal CBPs is related to n-body class of problems suggests applicability of a dual-tree approach. Algorithm 6provides a conceptual skeleton for the dual-tree algorithm we have developed to deal with CBP computations. Figure 8.: banana (1192x2). Representation of the reduced banana dataset. Following the structure laid out by the all-nearest-neighbors Algorithm 3, we start a depth-first dual-tree traversal where the reference nodes are compared to the leaf nodes: •At each step a possibility to prune the current pair (NRand NQ) is evaluated and the pruning is performed: CBP Prune (Section 3.1.2) •If the pair can not be pruned the recursive traversal through the current node descendants (NR.less/greater and NQ.less/greater) is continued until two leafs are reached. •As soon as the reference and query nodes represent leaf nodes, the CBP Local Search() (Section 3.1.6) is called. Its task is to locate the potential generating points (iand j) as well as potential intruding points kand extend the relevant lists with their indexes. After the dual-tree traversal has completed and we have filled lists of generating and intruding points, we feed these lists to the baseline Sokal Algorithm 4(slightly modified to work with adjusted inputs). Thus, the preprocessing with dual trees will help to reduce the search space that the Sokal has to operate on when applied to the raw datasets positively affecting the computation time. 36 3.1 faster cbp computations Algorithm 6:CBP Traversal. Dual-Tree traversal algorithm to find characterizing boundary points Input:NRreference node, NQquery node; i= [],j= [],k= [] three multidimensional lists, empty at the start Output:3multidimentional lists: i,j, and krepresenting the indexes of the data points from Mthat need to be evaluated by the Sokal algorithm begin // see Section 3.1.2 if CBP Prune(NR,NQ)then return; end if is lea f node(NR)and is lea f node(NQ)then // see Section 3.1.6 CBP Local Search(NR,NQ,i,j,k); else if is lea f node(NR)and !is lea f node(NQ)then CBP Traversal(NR,NQ.less,i,j,k); CBP Traversal(NR,NQ.greater,i,j,k); else if !is lea f node(NR)and is lea f node(NQ)then CBP Traversal(NR.less,NQ,i,j,k); CBP Traversal(NR.less,NQ,i,j,k); else if !is lea f node(NR)and !is lea f node(NQ)then CBP Traversal(NR.less,NQ.less,i,j,k); CBP Traversal(NR.less,NQ.greater,i,j,k); CBP Traversal(NR.greater,NQ.less,i,j,k); CBP Traversal(NR.greater,NQ.greater,i,j,k); end end 37 proposal 3.1.1Dual-Tree Architecture We have considered two different choices to partition the data. The first one is to construct two distinct kd-trees: one for XRand the other one for XQ. An alternative solution is to build one tree on the whole dataset Mirrespective of the class labels and reuse it during the dual-tree traversal. The result of both architectures are visualized in Figures 9and 10. The advantage of using two trees is the simplicity of implementation and the resulting dual-tree traversal. However, using a single tree on the whole dataset produces uniform tree cells which would prove critical during for the pruning strategies. In order to fully benefit from pruning, we have settled for the architecture where the same tree data structure is used for query and reference nodes. Figure 9.: Dual-tree architecture: one tree Figure 10.: Dual-tree architechture: two trees 3.1.2Pruning Rules We have devised several pruning rules to achieve two parallel objectives: 1) to implement a strict pruning rule that reduces the dataset by discarding only illegitimate points of the datasets, 2) to bring forth a more relaxed pruning rule that would offer a good compromise between improved efficiency and accuracy of the results. 3.1.3Exact CBP Computation Given that the Sokal algorithm finds all CBPs, the processing of the points after application of the strict pruning rule should provide results identical to the baseline solution. Conservative maximum distance pruning. Having partitioned the datasets either with a single or multiple tree, we can access the tree cells which contain data points clustered according to their spacial location. Consider a query and reference nodes as depicted in Figure 11. We want to prune these two nodes if it is certain that the 38 3.1 faster cbp computations other points located between the two nodes render their capacity to generate CBPs void. We can reverse the inequality Equation 7in order to identify non-generating points and substitute point-wise distances with distance measurements between the nodes, which renders Equation 10. dmin(NR,NQ)2≥dmax(NR,k)2+dmax(NQ,k)2(10) Thus, the first version of the pruning rule states that nodes NRand NQ– and therefore any points they contain – are not generating nodes if there exists a point kin the dataset the sum of maximum squared distances to each one of the nodes NRand NQis less than the minimum squared distance between those nodes. This rule is visualized in Figure 11. Remember, that we only have two cheap distance functions at our disposal: minimum and maximum distance. Having that in mind, note the role that the choice of min/max distance plays in the definition of the rule: 1. Minimum distance between two hyperrectangles dmin(NR,NQ)2 ensures that we consider the shortest possible distance between any two points belonging to the respective nodes. While the distance can be calculated, there is no information as to the exact location of those points. 2. Instead of the minimum distance, a maximum distance between hyperrectangles and point k–dmax(NR,k)2and dmax(NQ,k)2– is used to consider the distances between kand the furthest points in the hyperrectangle in order to ensure that point kwould break generating capacity of the most distant data points to it. Compare that to the alternative – using minimum distance – as indicated in on Figure 11 in red color. In that case, the formula would indicate that the two nodes can be pruned whereas that action would eliminate valid CBPs. While this rule is valid, it is overly conservative by considering the whole hyperrectangle areas when calculating the maximum distances dmax(NR,k)2and dmax(NQ,k)2. It is, in fact sufficient to calculate the maximum distance between kand the side of the hyperrectangle that faces the other hyperrectangle: see Figure 12. Maximum distance pruning. One possible solution could be to calculate all four distances in two dimensions, sort them, and take the second smaller distance which should be the furthest distance of the side facing the other node. However, this approach quickly becomes unfeasible in higher dimensions where the number of vertices 39 proposal Figure 11.: Pruning rule Figure 12.: Tighter pruning rule is 2d[26]. Instead, the proposed idea is to “squeeze” the hyperrectangles towards each other in order to produce modified tight rectangles. Afterwards we can apply a cheap maximum distance function to calculate the distance from the side of the rectangle to the point k (Figure 12). Figure 13 shows a possible worst case to justify the use of the maximum distance measure to the kfrom the tight nodes N0 R and N0 Q: using the minimum distance (indicated by dashed red colored lines) may in this case misleadingly suggest to prune the node 40 3.1 faster cbp computations Figure 13.: Worst case Figure 14.: Strict pruning in 3D pair, while a more conservative maximum distance measure ensures that the furthest points within the nodes are considered during the computation. 3.1.4Approximate CBP Computation Although a proposed conservative pruning strategy would lead to the exact CBP computation, as the experiments show, the rate of suc- 41 proposal •In order to accelerate the query performance, we have added an option to the kd-tree to perform approximate nearest-neighbor queries: instead of strictly fetching the specified by k-nearest neighbors, the query returns all the points within the cells that are at the specified distance. Setting nparameter to the size of the dataset achieves the desired result of filling a list of potential intruding points with indexes. 3.2 a cbp-based classifier One of the weaknesses of the original Boosted OGE classifier is its poor scalability in respect to the surge in dimension and size of underlying datasets. This goes back to the fact that the base classifiers are constructed on top of the CBPs. The author argues that the Boosted OGE’s subprime results on some of the datasets could be attributed to low number of base classifiers, due to the stringent rules of building CBPs. However, as we increase the dataset sizes and dimensions the number of CBPs has a drastic and unpredictable growth. Tables 1and 2expose the CPB growth. Table 1.: Growth of CBPs as dataset gains more dimensions EEGeye CBPs Twonorm CBPs Size Dim. (count) (%) Size Dim. (count) (%) 7200 2 9942 6660 2 3485 7200 4 11199 112.64 6660 4 9237 265.05 7200 6 17276 154.26 6660 6 22095 239.20 7200 8 34494 199.66 6660 8 44796 202.74 7200 10 48507 140.62 6660 10 78571 175.40 7200 12 69765 143.82 6660 12 132153 168.20 7200 14 69854 100.13 6660 14 201042 152.13 Table 2.: Growth of CBPs as dataset increases in size EEGeye CBPs Twonorm CBPs Size Dim. (count) (%) Size Dim. (count) (%) 1800 14 10751 1665 14 46354 3600 14 58785 546.79 3330 14 115334 248.81 5400 14 45827 77.96 4995 14 201042 174.31 7200 14 69854 152.43 6660 14 303220 150.82 48 3.2 a cbp-based classifier Consider, for instance, that we want to run Boosted OGE on EEG- eye dataset with 7200 instances and 10 dimensions, then the original Boosted OGE algorithm would need 1) to construct a matrix Aof base classifiers applied to the training dataset (resulting dimension is 7200x48507) and 2) to calculate the best performer at each boosting iteration in order to augment the set of the strong classifiers. Clearly, that introduces both immense storage but also computational complexity making the use of the classifier limited to the smaller datasets. We propose two alternative modifications to Boosted OGE to address its scalability issues (visualized in Figures 21 and 22). Figure 21.: Boosted OGE: filtered merge Figure 22.: Boosted OGE: cascade Both modifications apply ideas from divide-and-conquer algorithm design paradigm to reduce computational and storage costs. They, however, approach the task in somewhat different manner. Filtered merge (Figure 21). The first strategy is to split dataset in random feature subsets and to compute CBPs on these subsets. Afterwards, all the computed CBPs are merged into a single set and the base linear classifiers are built on top of them. While the default strategy is to merge all the CBPs together into one single set, we propose a selection criteria by which only a certain percentage of CBPs ranked according to their strength are chosen. We define strength 49 proposal as frequency with which the same CBP appears in different feature subsets; if there is no overlap between CBPs from different feature subsets, then the algorithm simply selects a given share of CBPs. Cascade (Figure 22) This modification resembles more the approach taken by random forest. Again, random feature sets are extracted from the dataset and the CBPs are computed based on them. However, instead of merging the CBPs into a single set, the cascade proceeds to generate base classifiers on each individual set, runs the boosting OGE on top of it and finally utilizes majority voting to make the prediction of the final label. Both of the proposed solutions should provide computational speed improvements and reduction of storage requirements. 1. As we have seen, we can expect less CBPs in lower dimensions than in higher. Although filtered merge by combining the CBPs into a single set can potentially undo the gain of operating in lower dimensions, the filtering procedure ensures that a threshold value for CBP count is not exceeded. 2. Having less base classifiers reduces the computational cost of boosting iterations. Moreover, it adds a nice property that portions of the algorithm can be trivially parallelized. Thus, we have obtained two models, tuned by the following parameters: 1) size of feature subsets, 2) number of CBP generators (filtered merge) or CBP generators/classifiers (cascade). 50 4 EXPERIMENTS AND RESULTS 4.1 understanding the model Prior to jumping to the final results obtained with our algorithm, this section will attempt to give insight into the various factors of the model that are otherwise too easy to overlook if only the final values are considered. To support the findings, we would interchangeably consider only a small selection of the datasets as they adequately reflect general patterns of the model. Specifically, we will discover the effects that leaf size of the underlying kd-trees, dimensionality of the dataset, and local search have on our dual-tree algorithm for faster CBP computations. This will be followed by the analysis of aspects related to the proposed modifications of the Boosted OGE classifiers: effect of thresholding on the CBP count, performance of the classifier based on genuine or weak CBPs. Table 3.: Datasets Dataset Size Dim banana 5300 2 EEGEye 14980 14 Example 1014 5 magic 19020 10 ringnorm 7400 20 skin 245057 3 svmguide1 3089 4 transfusion 748 4 Twonorm 7400 20 waveform 5000 21 Table 3lists the original datasets that have been used in the experiments (Table 11 in Appendix A provides the sources of these datasets). In order to explore effects of dimensionality and size but also to ensure that available hardware resources are able to operate 51 experiments and results on the datasets, these where reduced in dimensions and size. To provide reader with information about which particular version of the dataset is used in an experiment, we follow the convention of writing the name of the dataset followed by “(size xdimension)” information. 4.1.1Effect of Leaf Size We have conjectured (Section 2.1) about the influence that the leaf size setting can have on our algorithm: while small value for the number of data points in leaf nodes leads to expensive dual-tree traversals, too large values would convert the kd-tree queries to a brute force procedure. However, the true situation in context of the CBP computations appears to have even more variability. Figure 23.: EEGEye (7200x2): Leaf size growth Figures 23 and 24 demonstrate the impact that the set leaf size (as percentage of the dataset size) values have on the time performance of the dual-tree algorithms compared to the baseline. While the relation between leaf size and execution ratio is clearly defined in a two-dimensional space, the picture is more vague in four dimensions. After a sharp rise in computation cost further increases in leaf sizes (19-31%) seem to have no correlation with algorithm performance. We can take a look at the leaf size problem from a different perspective plotting the breakdown between dual-tree time and CBP computation time: Figures 25 and 26 represent performance of the 52 4.1 understanding the model Figure 24.: EEGEye (7200x4): Leaf size growth conservative strategy for different leaf sizes. Figure 25.: EEGEye (7200x2): Break-down of dual-tree algorithm (conservative pruning) time consumption. 53 experiments and results Figure 26.: EEGEye (7200x4): Break-down of dual-tree algorithm (conservative pruning) time consumption. Both in two and four dimensional datasets dual-tree traversal corresponds to a significant portion of the total execution time. This implies that the algorithm is hard at work pruning the dataset and performing local search leading to the reduced time needed for the CBP computation. This relative ratio of dual-tree to CBP computation components gets distorted when the nodes become larger limiting the capacity of dual-tree traversal. However, the question of the sudden performance plunge in EEG- Eye (7400x4) as well as reasonably good results for higher leaf sizes are still puzzling until we look at Figures 27 and 27. The graphs demonstrate percentage of worst-case computations that the dual-tree versions have to perform as a percentage of the baseline Sokal worst case. Whereas the Sokal worst case is calculated as |NR|∗|NQ|∗|NR∪NQ|, the dual tree worst case is defined by ∑|S| s=1|NRs|∗|SQs|∗|SRs∪SQs|, where Sis a set of subspaces that are extracted from NR,NQ, and NQ∪NRduring the local search stage of the dual-tree traversal. As can be seen, growing node sizes correspond to the general increase of computation count. While the trend is stronger in two dimensions, it is still notable in the four-dimensional dataset. The execution time bump reported in the EEGEye (7200x4) dataset is likely 54 4.1 understanding the model Figure 27.: EEGEye (7400x2). Worst case vs real computations in relation to the leaf size Figure 28.: EEGEye (7400x4). Worst case vs real computations in relation to the leaf size an outlier that can be ignored, as the computation time diverges from the real computations line without any underlying cause (for instance, the dual-tree traversal time at this leaf size can be neglected, as indi- 55 experiments and results cated in Figure 26). The sudden rise could be caused by numeric calculations made by the Sokal subtask. Another interesting observation is the ever increasing gap between worst case and real computations. This particularity has less to do with the leaf size, but is rather a property of local search which is investigated in Section 4.1.3. We have settled to run the experiments with a leaf size set to 3% of the dataset as it seems to be a value at which the combination of dual-tree traversal and CBP computations are well-balanced and exhibit superior performance. Nevertheless, while outside of the report scope, the issue of optimal setting for leaf sizes as proportion of the dataset size and dimension needs further investigation. 4.1.2Effect of Dimensionality Figure 29.: Absolute time performance of Sokal and Dual-Tree algorithms as dataset dimensionality increases. Figures 29 and 30 demonstrate a general behavior of Sokal and dual-trees with three pruning strategies. While the data is based on dataset EEGEye, the trend of worsening performance is observed across all datasets. Two aspects are of particular importance to us: 1) the increase of computational time of the Sokal algorithm as the dimensions grow, 2) the steep increase of the dual-tree solutions. In a 2-dimensional space the dual-tree algorithm demonstrate over a one 56 4.1 understanding the model Figure 30.: Relative time performance of Dual-Tree algorithms compared to Sokal in as dataset dimensionality increases. order of magnitude performance improvement over the Sokal. That gain, however washes off as we go into the higher dimensions until the relative performance of the dual-tree even outs at 12 to 14 dimensions to be merely twice as fast as Sokal. One valuable observation that we can gain from Figure 30 is that at around 10 dimensions, all three versions of the dual-tree algorithms – conservative, minimum distance and nonadjacent pruning strategies – gravitate toward similar execution times. We can conclude than, that at that point, it is not the pruning strategies that distinguish each version but rather some other common factor that aligns their performance. Section 4.1.3looks deeper into the role the local search plays in the performance yields we have witnessed. 4.1.3Effect of Local Search As mentioned in Section 3.1.6, local search fulfills two goals: in lower dimensions due to application of the sphere boundary we are able to achieve the reduction of the potential intruding points. This additional pruning ability is not sustainable in higher dimensions due to the “curse of dimensionality” (see Section 4.1.4). In addition, the underlying k-nearest neighbor query introduces the space-aware metaheuristic which the baseline Sokal lacks: the 57 experiments and results Figure 35.: Time performance of the three dual trees in relation to Sokal (found by Sokal) and those based on the approximate points render almost identical results in respect to the accuracy percentage. Simultaneously, the dual-tree solution manages to beat the Sokalbased ensemble on each dataset in terms of time: the mere exception is dataset Example (912x5) where due to the poor data-samples-to- feature-count ratio the kd-trees become inefficient. Some of the values are not available (N/A) due to the growing storage cost: as we ascend into higher dimensions, the Boosted OGE algorithm has to create classifiers based on the growing number of points which does not fit into the memory leading to the algorithm failure. Table 7.: Validation of the CBPs found with dual-tree nonadjacent pruning against baseline Boosted OGE classifier Dataset Sokal Dual Tree (nonadjacent) Time Acc. Time Rel.time Acc. (s) (%) (s) (%) (%) banana (4770x2)73 59.25 9 12.44 59.25 EEGEye (7200x2)273 54.38 36 13.16 54.38 EEGEye (7200x4)427 65.63 88 20.60 65.63 EEGEye (7200x6)603 67.88 179 29.64 67.88 EEGEye (7200x8)1016 77.25 465 45.75 77.25 EEGEye (7200x10)1296 78.38 676 52.17 78.38 EEGEye (7200x12)1503 N/A 792 52.70 N/A 64 4.2 results Table 7.: Validation of the CBPs found with dual-tree nonadjacent pruning against baseline Boosted OGE classifier Dataset Sokal Dual Tree (nonadjacent) Time Acc. Time Rel.time Acc. (s) (%) (s) (%) (%) EEGEye (7200x14)1485 N/A 788 53.07 N/A Example (912x2)3 62.75 1 19.44 62.75 Example (912x4)5 88.24 4 76.90 88.24 Example (912x5)5 100.00 8 157.95 100.00 magic (7200x2)376 72.50 52 13.95 72.50 magic (7200x4)668 78.63 130 19.45 78.63 ringnorm (6660x2)311 73.78 49 15.72 73.78 ringnorm (6660x4)675 83.24 134 19.81 83.24 ringnorm (6660x6)823 84.59 420 51.00 84.59 skin (7200x2)131 20.00 23 17.43 20.00 skin (7200x3)88 98.88 19 21.05 98.25 svmguide1(2780x2)17 94.17 1 8.70 94.17 svmguide1(2780x4)23 97.09 12 51.79 97.09 transfusion (673x2)8 82.67 2 28.95 82.67 transfusion (673x4)5 82.67 1 27.81 82.67 Twonorm (6660x2)216 71.62 32 14.86 71.62 Twonorm (6660x4)437 80.54 171 39.20 80.54 Twonorm (6660x14)4138 N/A 2346 56.70 N/A waveform (4500x2)148 68.40 16 10.66 68.40 waveform (4500x4)400 67.00 137 34.17 67.00 waveform (4500x8)672 80.80 406 60.46 80.80 4.2.2A CBP-Based Classifier Having confirmed comparable accuracy achieved by the dual tree algorithms we would now proceed to the analysis of the alternative ensemble classifiers. The reader can refer to the detailed results in Table 10 of Appendix A whereas this section concentrates on the main aspects. Among the three proposed classifiers – merge all,filtered merge (25% and 50%), and cascade – only the last two will be extensively analyzed in this section. The reason for this is, as also visible in Table 10, that we can discard two classifiers from the detailed analysis: 1)full merge tends to amass disproportionately many CBPs leading to the excessive memory load; 2) as filtered merge with thresholds 25% and 50% exhibit comparable performance we will only consider the former pa- 65 experiments and results rameterization of the classifier. Figure 36.: Comparison of relative computation time with classifier accuracy Figure 36 puts a dual perspective on the performance of the classifiers: relative computation time compared to Sokal vs classifier accuracy. Instead of presenting the datasets with different feature subsets as was done in 7, Figure 36 selects one particular feature subset of the dataset. Generally, a dataset with most complete feature set was taken except when it was impractical as at least one of the classifiers would collapse due to the storage cost of fitting multitude of resulting CBPs. We observe that typically both cascade and filtered merge classifiers outperform Sokal in terms of computational time. A notable exception is dataset Example (912x5) where due to the relatively small size of the dataset, the new classifiers can not keep up with Sokal. Barring for the datasets skin and banana, both cascade and filtered merge have commensurate performance with Sokal in terms of accuracy. While cascade performance is sensitive to the value of the features used for the subclassifiers, being only 3-dimensional, dataset skin leaves no space for the classifier improvement which could be said to be unsuitable for the particular problem. On the other hand, filtered merge displays admirable outstanding accuracy on the 2-d dataset, where both Sokal and cascade are about 30% behind. 66 4.2 results Table 8.: Ranking of classifiers according to accuracy Dataset Sokal Filtered Cascade Random merge 25% Forest banana (4770x2)59.25 89.81 59.25 91.32 EEGEye (7200x10)78.38 74.38 75.00 86.00 Example (912x5)100.00 100.00 99.02 100.00 magic (7200x4)78.63 78.38 68.63 78.38 ringnorm (6660x6)84.59 83.78 82.03 86.89 skin (7200x3)98.88 95.50 20.00 99.75 svmguide1(2780x4)97.09 96.44 94.17 96.76 transfusion (673x2)82.67 82.67 82.67 78.67 Twonorm (6660x4)80.54 78.78 78.38 76.08 waveform (4500x8)80.80 82.00 75.40 77.60 Rank 1.6 2.2 3.1 1.7 Given that Sokal falls behind on the larger datasets in terms of time, we aim the analysis on the accuracy aspect for the datasets that are solvable by Sokal. Table 8is a ranking of the classifiers. We provide reference values for the results obtained with the random forest classifier in order to have an additional benchmark values. Sokal has a narrow lead over filtered merge strategy with cascade trailing behind. It is interesting to observe, that filtered merge, although ranked to be the 3rd if only considering the raw values, has a very close general performance with the random forest classifier, should we allow for a tolerance value of 5% with respect to the accuracy values. Figure 37 gives another view angle on the classification of the datasets which the Boosted OGE classifier failed to crunch due to the storage capacity required by the growing number of CBPs. The time values are absolute because a baseline measurements are missing. We can, nevertheless, see that the filtered merge outperforms cascade in computation by a wide margin while both classifiers have achieved similar accuracy rates. Furthermore, the algorithms are able to capitalize on growing number of features and consequently outperform the Boosted OGE values achieved on the lower dimensional datasets. Accordingly, as we go into higher dimensions and the storage cost becomes unbearable for the baseline Boosted OGE, we can resort to the proposed alternative ensemble-based models. Based on the experimental data, the transition from an “integral” to an ensemble-based model incurs no significant penalty in terms of prediction ability of the classifiers. 67 experiments and results Figure 37.: Comparison of computation time with classifier accuracy for higher dimensions 68 5 CONCLUSIONS AND FUTURE WORK conclusions. This work has started off with the exploration of the dual-tree framework that was originally devised to bring tractability to the class of generalized n-body problems. We have been able to devise a dual-tree based algorithm to deal with the problem of finding characterizing boundary points (CBP), a special case of the Gabriel graph. The proposed algorithm was devised in incremental fashion, proposing and evaluating alternative solutions to the dual-tree architecture, pruning rules, and a local search strategy. In this course, we have been able to devise two types of pruning – exact and approximate – offering a trade-off between accuracy of CBP computation and speed gains. Owing to the powerful metaheuristics implemented by the local search and reduction of the dataset brought about by pruning, the developed dual-tree algorithm has been able to both lower worst-case and real-case computation measurements as compared to the baseline Sokal solution. Based on the experimental evaluation, we have been able to achieve about an order of magnitude performance increases on the two-dimensional datasets. Gains in efficiency were also evident in higher dimensions ranging from 70% to 50% improvement of the state-of-the-art method. Having built a new algorithm for finding CBPs we have proceeded to Boosted OGE [23], a CBP-based classification algorithm. We have set a goal of improving one of the algorithm’s weaknesses – poor scalability in higher dimensions. In order to do that, two alternative models where proposed that integrated original problem-solving approach of the classifier into an ensemble-based framework. Both models – filtered merge and cascade – were shown to be on par with the original classifier in terms of predictive power on almost all datasets, while outperforming it in computational speed. Above all, however, the two ensemble-based models have been able to take up larger datasets which the original Boosted OGE algorithm fails to tackle due to the high memory cost it requires. 69 conclusions and future work future work. This work has opened up a number of areas that further research should address. CBP Computation. The proposed dual-tree algorithm is superior to Sokal in performance, but also more complex as it requires parameterizing the node size. Experimentally shown to be an important factor for the dual-tree performance and a non-trivial task, a stricter methodology or a set of general observations should be developed to determine optimal values for the leaf sizes. This would inevitably depend on the implicit dimensionality of the datasets and their sizes and is likely to be specific to the chosen dual-tree architecture. It has been demonstrated that approximation strategies do not affect the performance of the CBP-based classifier. Therefore, we could hypothesize that even more aggressive pruning rules and restricted local search could bring computational speed dividends without sacrifices of the performance. Having observed the non-linear growth of CBPs attributed to the rise of dimensionality, we can even argue that tightening the number of discovered CBPs may implicitly obtain needed regularization in higher dimensions. More awareness about the required size of the datasets in respect to their implicit dimension is needed to be able to conclude beforehand about the expected performance gain of the dual-tree algorithms compared to Sokal. Due to the hardware considerations we were restricted in the size of the datasets under test. CBP-Based Classifier. The two developed ensemble-based models proposed have a comparable performance to the original Boosted OGE classifier. However, inspecting the CBPs that the ensemble learners operate on has shown that they share only a small margin of the “genuine” CBPs. This fact seems to have no adverse effect on the classification, but needs a more rigorous study of its own. Being just a heuristic notion of goodness, CBPs do not necessarily represent the most optimal imaginary classification boundary, whereas the newly found “weak CBPs” could embody a better approximation. The proposed filtered merge has proven to be robust to thresholding as we have reduced the number of points retained from 50% to 25%. Reducing the number of CBPs further will cut down the dimensions of the ensuing weak classifiers, therefore it is certainly worthy to test the limits of thresholding. Furthermore, instead of setting a percentage threshold the filtered merge can be set to retain a certain number of CBPs based on the underlying dataset size and dimension. 70 BIBLIOGRAPHY [1] Jon Louis Bentley. “Multidimensional binary search trees used for associative searching”. In: Commun. ACM 18 (9 1975), pp. 509–517.issn:0001-0782.doi:10 . 1145 / 361002 . 361007. url:http://doi.acm.org/10.1145/361002.361007. [2] Mark de Berg et al. Computational Geometry: Algorithms and Applications.3rd ed. Santa Clara, CA, USA: Springer-Verlag TELOS, 2008.isbn:3540779736,9783540779735. [3] Wikimedia Commons. A3-dimensional k-d tree. File: 3dtree.png. 2015.url:http : / / commons . wikimedia . org / wiki / File : 3dtree.png. [4] Wikimedia Commons. Gabriel graph. File: Gabriel graph.svg. 2015.url:http : / / commons . wikimedia . org / wiki / File : Gabriel_graph.svg. [5] Wikimedia Commons. Nearest neighbor graph. File: Nearest neighbor graph.svg.2015.url:http : / / commons . wikimedia.org/wiki/File:Nearest_neighbor_graph.svg. [6] Jacob E. Goodman Csaba D. Toth Joseph O’Rourke. Handbook of Discrete and Computational Geometry, Second Edition. Apr. 13, 2004. [7] Ryan R. Curtin et al. “Tree-Independent Dual-Tree Algorithms”. In: CoRR abs/1304.4327 (2013). url:http://dblp.uni-trier. de/db/journals/corr/corr1304.html#abs-1304-4327. [8] Pedro Domingos. “A Few Useful Things to Know About Machine Learning”. In: Commun. ACM 55.10 (Oct. 2012), pp. 78–87. issn:0001-0782.doi:10.1145/2347736.2347755.url:http: //doi.acm.org/10.1145/2347736.2347755. [9] Jerome H. Friedman, Jon Louis Bentley, and Raphael Ari Finkel. “An Algorithm for Finding Best Matches in Logarithmic Expected Time”. In: ACM Trans. Math. Softw. 3.3(Sept. 1977), pp. 209–226.issn:0098-3500.doi:10 . 1145 / 355744 . 355745. url:http://doi.acm.org/10.1145/355744.355745. [10] K. R. Gabriel and R. R. Sokal. “A new statistical approach to geographic variation analysis”. In: Syst. Zool. (1969), pp. 259– 278. [11] Alexander Gray and Andrew Moore. “‘N-Body’ Problems in Statistical Learning”. In: Advances in Neural Information Processing Systems 13. MIT Press, 2000, pp. 521–527. 71 Bibliography [12] Alexander G. Gray. “Bringing Tractability to Generalized N- Body Problems in Statistical and Scientific Computation”. PhD thesis. Carnegie Mellon University, 2003. [13] Alexander G Gray. Fast N-Body Algorithms for Massive Datasets. https://www.siam.org/meetings/sdm08/TS3.ppt. (Visited on 04/15/2015). [14] Alexander G. Gray and Andrew W. Moore. “Nonparametric Density Estimation: Toward Computational Tractability”. In: SDM. Ed. by Daniel Barbar and Chandrika Kamath. SIAM, Aug. 26,2003.isbn:0-89871-545-8.url:http : / / dblp . uni - trier.de/db/conf/sdm/sdm2003.html#GrayM03. [15] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer Series in Statistics. New York, NY, USA: Springer New York Inc., 2001. [16] Eric Jones, Travis Oliphant, Pearu Peterson, et al. SciPy: Open source scientific tools for Python. [Online; accessed 2015-04-06]. 2001.url:http://www.scipy.org/. [17] Songrit Maneewongvatana and David M. Mount. “It’s Okay to Be Skinny, If Your Friends Are Fat”. In: Center for Geometric Computing 4th Annual Workshop on Computational Geometry.1999. [18] David W. Matula and Robert R. Sokal. “Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane”. In: Geographical Analysis 12.3 (1980), pp. 205–222.issn:1538-4632.doi:10 . 1111 / j . 1538 - 4632.1980.tb00031.x.url:http://onlinelibrary.wiley. com/doi/10.1111/j.1538-4632.1980.tb00031.x/abstract. [19] Andrew Moore and Mary Soon Lee. “Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets”. In: Journal of Artificial Intelligence Research 8(1997), pp. 67–91. [20] Andrew W. Moore. “The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data”. In: In Twelfth Conference on Uncertainty in Artificial Intelligence. AAAI Press, 2000, pp. 397–405. [21] AndrewW. Moore et al. “Fast Algorithms and Efficient Statistics: N-Point Correlation Functions”. English. In: Mining the Sky. Ed. by AnthonyJ. Banday, Saleem Zaroubi, and Matthias Bartelmann. ESO ASTROPHYSICS SYMPOSIA. Springer Berlin Heidelberg, 2001, pp. 71–82.isbn:978-3-540-42468-0.doi:10.1007/ 10849171_5.url:http://dx.doi.org/10.1007/10849171_5. [22] F. Pedregosa et al. “Scikit-learn: Machine Learning in Python”. In: Journal of Machine Learning Research 12 (2011), pp. 2825–2830. 72 Bibliography [23] Oriol Pujol. “Boosted Geometry-Based Ensembles.” In: MCS. Ed. by Neamat El Gayar, Josef Kittler, and Fabio Roli. Vol. 5997. Lecture Notes in Computer Science. Springer, Apr. 14,2010, pp. 195–204.isbn:978-3-642-12126-5.url:http://dblp.unitrier.de/db/conf/mcs/mcs2010.html#Pujol10. [24] Oriol Pujol and David Masip. “Geometry-Based Ensembles: Toward a Structural Characterization of the Classification Boundary.” In: IEEE Trans. Pattern Anal. Mach. Intell. 31.6(2009), pp. 1140–1146.url:http : / / dblp . uni - trier . de / db / journals/pami/pami31.html#PujolM09. [25] Remco C. Veltkamp. Closed Object Boundaries from Scattered Points. Nov. 30,1994. [26] Eric W. Weisstein. Hypercube. From MathWorld—A Wolfram Web Resource. Last visited on 4/4/2015.url:http: / /mathworld . wolfram.com/Hypercube.html. [27] Eric W. Weisstein. Space diagonal. From MathWorld—A Wolfram Web Resource. Last visited on 4/4/2015.url:http : / / mathworld.wolfram.com/SpaceDiagonal.html. 73