flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-1745) Add exact k-nearest-neighbours algorithm to machine learning library
Date Wed, 14 Oct 2015 13:35:05 GMT

    [ https://issues.apache.org/jira/browse/FLINK-1745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14956944#comment-14956944
] 

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_r41992974
  
    --- 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)
    +
    +      }
    --- End diff --
    
    The reason for this was that we didn't want to reimplement a linear algebra library. And
at the same time we didn't want the people to lock in on one specific library. So theoretically,
you could also use a different math backend. You just have to convert it from `Vector` to
the library specific type.


> 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)

Mime
View raw message