[
https://issues.apache.org/jira/browse/FLINK-1745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14948354#comment-14948354
]
ASF GitHub Bot commented on FLINK-1745:
---------------------------------------
Github user tillrohrmann commented on a diff in the pull request:
https://github.com/apache/flink/pull/1220#discussion_r41492452
--- Diff:
flink-staging/flink-ml/src/main/scala/org/apache/flink/ml/nn/QuadTree.scala ---
@@ -0,0 +1,305 @@
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.ml.nn.util
+
+import org.apache.flink.ml.math.Vector
+import org.apache.flink.ml.metrics.distances.DistanceMetric
+
+import scala.collection.mutable.ListBuffer
+import scala.collection.mutable.PriorityQueue
+
+/**
+ * n-dimensional QuadTree data structure; partitions
+ * spatial data for faster queries (e.g. KNN query)
+ * The skeleton of the data structure was initially
+ * based off of the 2D Quadtree found here:
+ *
http://www.cs.trinity.edu/~mlewis/CSCI1321-F11/Code/src/util/Quadtree.scala
+ *
+ * Many additional methods were added to the class both for
+ * efficient KNN queries and generalizing to n-dim.
+ *
+ * @param minVec
+ * @param maxVec
+ */
+class QuadTree(minVec:ListBuffer[Double],
maxVec:ListBuffer[Double],distMetric:DistanceMetric){
+ var maxPerBox = 20
+
+ class Node(c:ListBuffer[Double],L:ListBuffer[Double], var
children:ListBuffer[Node]) {
+
+ var objects = new ListBuffer[Vector]
+
+ /** for testing purposes only; used in QuadTreeSuite.scala
+ *
+ * @return
+ */
+ def getCenterLength(): (ListBuffer[Double], ListBuffer[Double]) = {
+ (c, L)
+ }
+
+ def contains(obj: Vector): Boolean = {
+ overlap(obj, 0.0)
+ }
+
+ /** Tests if obj is within a radius of the node
+ *
+ * @param obj
+ * @param radius
+ * @return
+ */
+ def overlap(obj: Vector, radius: Double): Boolean = {
+ var count = 0
+ for (i <- 0 to obj.size - 1) {
+ if (obj(i) - radius < c(i) + L(i) / 2 && obj(i) + radius > c(i) -
L(i) / 2) {
+ count += 1
+ }
+ }
+
+ if (count == obj.size) {
+ return true
+ } else {
+ return false
+ }
+ }
+
+ /** Tests if obj is near a node: minDist is defined so that every
point in the box
+ * has distance to obj greater than minDist
+ * (minDist adopted from "Nearest Neighbors Queries" by N.
Roussopoulos et al.)
+ *
+ * @param obj
+ * @param radius
+ * @return
+ */
+ def isNear(obj: Vector, radius: Double): Boolean = {
+ if (minDist(obj) < radius) {
+ true
+ } else {
+ false
+ }
+ }
+
+ def minDist(obj: Vector): Double = {
+ var minDist = 0.0
+ for (i <- 0 to obj.size - 1) {
+ if (obj(i) < c(i) - L(i) / 2) {
+ minDist += math.pow(obj(i) - c(i) + L(i) / 2, 2)
+ } else if (obj(i) > c(i) + L(i) / 2) {
+ minDist += math.pow(obj(i) - c(i) - L(i) / 2, 2)
+ }
+ }
+ return minDist
+ }
+
+ def whichChild(obj:Vector):Int = {
+
+ var count = 0
+ for (i <- 0 to obj.size - 1){
+ if (obj(i) > c(i)) {
+ count += Math.pow(2,i).toInt
+ }
+ }
+ count
+ }
+
+ def makeChildren() {
+ var cBuff = new ListBuffer[ListBuffer[Double]]
+ cBuff += c
+ var Childrennodes = new ListBuffer[Node]
+ val cPart = partitionBox(cBuff,L,L.length)
+ for (i <- cPart.indices){
+ Childrennodes = Childrennodes :+ new Node(cPart(i), L.map(x =>
x/2.0), null)
+
+ }
+ children = Childrennodes.clone()
+ }
+
+ /**
+ * Recursive function that partitions a n-dim box by taking the (n-1)
dimensional
+ * plane through the center of the box keeping the n-th coordinate
fixed,
+ * then shifting it in the n-th direction up and down
+ * and recursively applying partitionBox to the two shifted (n-1)
dimensional planes.
+ *
+ * @param cPart
+ * @param L
+ * @param dim
+ * @return
+ */
+ def
partitionBox(cPart:ListBuffer[ListBuffer[Double]],L:ListBuffer[Double],
dim:Int):
+ ListBuffer[ListBuffer[Double]]=
+ {
+ if (L.length == 1){
+
+ var cPartDown = cPart.clone()
+ //// shift center up and down
+ val cPartUp = cPart.map{v => v.patch(dim-1, Seq(v(dim - 1) +
L(dim-1)/4), 1)}
+ cPartDown = cPartDown.map{v => v.patch(dim-1, Seq(v(dim - 1) -
L(dim-1)/4), 1)}
+
+ return cPartDown ++ cPartUp
--- End diff --
returns are not very scalaesque. Why not putting the following code in an
`else` branch?
> Add exact k-nearest-neighbours algorithm to machine learning library
> --------------------------------------------------------------------
>
> Key: FLINK-1745
> URL: https://issues.apache.org/jira/browse/FLINK-1745
> Project: Flink
> Issue Type: New Feature
> Components: Machine Learning Library
> Reporter: Till Rohrmann
> Assignee: Daniel Blazevski
> Labels: ML, Starter
>
> Even though the k-nearest-neighbours (kNN) [1,2] algorithm is quite trivial
> it is still used as a mean to classify data and to do regression. This issue
> focuses on the implementation of an exact kNN (H-BNLJ, H-BRJ) algorithm as
> proposed in [2].
> Could be a starter task.
> Resources:
> [1] [http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm]
> [2] [https://www.cs.utah.edu/~lifeifei/papers/mrknnj.pdf]
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
