k-Nearest Neighbors关联

描述

实现精确的k近邻连接算法。给出训练集一个和测试集,算法返回

ķ N N Ĵ一个ķ={bķ N N b一个ķ 哪里 b 和 ķ N N b一个ķ 是最近的k点 b 在 一个}

蛮力方法是计算每个训练点和测试点之间的距离。为了简化计算每个训练点之间距离的强力计算,使用四叉树。四叉树在训练点的数量上很好地扩展,但在空间维度上很差。该算法将自动选择是否使用四叉树,但用户可以通过设置参数来强制使用或不使用四叉树来覆盖该决策。

算子操作

KNN是一个Predictor因此,它支持fitpredict 算子操作。

适合

KNN由一组给定的训练Vector

  • fit[T <: Vector]: DataSet[T] => Unit

预测

KNN预测FlinkML的所有子类型Vector对应的类标签:

  • predict[T <: Vector]: DataSet[T] => DataSet[(T, Array[Vector])](T, Array[Vector])元组对应的(测试点,K-最近的训练点)

参数

KNN实现可以通过以下参数控制:

参数 描述
ķ

定义要搜索的最近邻居数。也就是说,对于每个测试点,算法在训练集中找到K-最近邻居(默认值:5

DistanceMetric

设置我们用于计算两点之间距离的距离度量。如果未指定度量标准,则使用[[org.apache.flink.ml.metrics.distances.EuclideanDistanceMetric]]。(默认值:EuclideanDistanceMetric

设置输入数据将被分割到的块数。此数字应至少设置为并行度。如果未指定任何值,则输入[[DataSet]]的并行性将用作块数。(默认值:

UseQuadTree

一个布尔变量,无论是否使用四叉树来划分训练集,都可能简化KNN搜索。如果未指定任何值,代码将自动决定是否使用四叉树。四叉树的使用与训练和测试点的数量很好地对应,但是尺寸很差。(默认值:

SizeHint

指定训练集或测试集是否很小,以优化KNN搜索所需的跨产品 算子操作。如果训练集很小,则应该是“CrossHint.FIRST_IS_SMALL”并且如果测试集很小则设置为“CrossHint.SECOND_IS_SMALL”。(默认值:

例子

import org.apache.flink.api.common.operators.base.CrossOperatorBase.CrossHint
import org.apache.flink.api.scala._
import org.apache.flink.ml.nn.KNN
import org.apache.flink.ml.math.Vector
import org.apache.flink.ml.metrics.distances.SquaredEuclideanDistanceMetric

val env = ExecutionEnvironment.getExecutionEnvironment

// prepare data
val trainingSet: DataSet[Vector] = ...
val testingSet: DataSet[Vector] = ...

val knn = KNN()
  .setK(3)
  .setBlocks(10)
  .setDistanceMetric(SquaredEuclideanDistanceMetric())
  .setUseQuadTree(false)
  .setSizeHint(CrossHint.SECOND_IS_SMALL)

// run knn join
knn.fit(trainingSet)
val result = knn.predict(testingSet).collect()

有关使用和不使用和四叉树计算KNN的更多详细信息,请参阅以下内容:http//danielblazevski.github.io/

回到顶部

原文