这是一个有趣的问题！有两件事使它特别具有挑战性：

• 我们应该如何比较两个点集？机器学习中的经典问题具有固定数量的属性，并且这些属性不可互换：例如，我可能拥有不同人的数据，具有属性age和height（以厘米为单位）。每个样本都有一个条目，当然(age, height) = (22, 180)与(age, height) = (180, 22). 你的问题也不是真的。一个点集有 3 到 10 个点，在比较两个点集时，我们输入点的顺序不应该有区别。
• 我们如何做出预测？假设我们找到了一种从我们的训练集中选择与上面的点集相似的点集的方法。我们面临的问题是我们的预测必须是您图片中的 7 个点之一；但是这些点中没有一个可能包含在相似的点集中。

让我概述一个处理这两个挑战的算法。预测精度不是很好；但也许你看到了如何改进它的方法。至少它预测了一些东西，对吧？

1. 模拟样品

为了能够测试算法，我编写了生成样本和标签的函数。

生成样本： 每个样本包含 3 到 10 个点。点的数量是随机的，从均匀分布中抽取。每个点的形式为(x_coordinate, y_coordinate)。坐标也是随机的，从正态分布中得出。

import numpy as np
from random import randint

def create_samples(number_samples, min_points, max_points):

    def create_single_sample(min_points, max_points):
        n = randint(min_points, max_points)
        return np.array([np.random.normal(size=2) for _ in range(n)]) 

    return np.array([create_single_sample(min_points, max_points) for _ in range(number_samples)])

生成标签：作为一个玩具示例，让我们假设选择点的规则是：始终选择最接近 的点(0, 0)，其中“最接近”应该根据欧几里得范数来理解。

def decision_function_minnorm(sample):
    norms = np.apply_along_axis(np.linalg.norm, axis=1, arr=sample)
    return sample[norms.argmin()]

def create_labels(samples, decision_function):
    return np.array([decision_function(sample) for sample in samples])

我们现在可以创建我们的训练和测试集：

n_train, n_test = 1000, 100
dec_fun = decision_function_minnorm

X_train = create_samples(number_samples=n_train, min_points=3, max_points=10)
X_test = create_samples(number_samples=n_test, min_points=3, max_points=10)
y_train = create_labels(X_train, dec_fun)
y_test = create_labels(X_test, dec_fun)

2. 通过 Hausdorff 距离比较点集

让我们解决第一个问题：我们应该如何比较不同的点集？点集中的点数不同。还要记住，我们写下点的顺序无关紧要：与点集比较[(0,0), (1,1), (2,2)]应该产生与与点集比较相同的结果[(2,2), (0,0), (1,1)]。我的方法是通过它们的Hausdorff 距离来比较点集：

def hausdorff(A, B):

    def dist_point_to_set(x, A):
        return min(np.linalg.norm(x - a) for a in A)

    def dist_set_to_set(A, B):
        return max(dist_point_set(a, B) for a in A)

    return max(dist_set_to_set(A, B), dist_set_to_set(B, A))

3.通过k近邻进行预测并取平均值

我们现在有了点集之间距离的概念。这使得使用 k 最近邻分类成为可能：给定一个测试点集，我们k在训练样本中找到相对于测试点集具有最小 Hausdorff 距离的点集，并获得它们的标签。现在来了第二个问题：我们如何将这些k标签变成对测试点集的预测？我采用了最简单的方法：平均标签并预测测试点集中最接近平均值的点。

def predict(x, num_neighbors):
    # Find num_neighbors closest points in X_train.
    distances_to_train = np.array([hausdorff(x, x_train) for x_train in X_train])
    neighbors_idx = np.argpartition(distances_to_train, -num_neighbors)[-num_neighbors:]

    # Get labels of the neighbors and calculate the average.
    targets_neighbors = y_train[neighbors_idx]
    targets_mean = sum(targets_neighbors) / num_neighbors

    # Find point in x that is closest to targets_mean and use it as prediction.
    distances_to_mean = np.array([np.linalg.norm(p - targets_mean) for p in x])
    closest_point = x[distances_to_mean.argmin()]

    return closest_point

4. 测试

一切就绪，可以测试我们算法的性能。

num_neighbors = 70
successes = 0
for i, x in enumerate(X_test):
    print('%d/%d' % (i+1, n_test))
    prediction = predict(x, num_neighbors)
    successes += np.array_equal(prediction, y_test[i])

对于给定的决策函数 和num_neighbors = 70，我们得到 84% 的预测准确率。这不是非常好，而且它当然是特定于我们的决策功能，这似乎很容易预测。

要看到这一点，请定义一个不同的决策函数：

decision_function_maxaverage(sample):
    avgs = (sample[:, 0] + sample[:, 1]) / 2
    return sample[norms.argmin()]

通过使用此功能可dec_fun = decision_function_maxaverage将预测准确率降低到 45%。这表明考虑生成标签的决策规则是多么重要。如果您知道人们为什么选择某些点，这将帮助您找到最佳算法。

改进该算法的一些方法：(1) 使用不同的距离函数而不是 Hausdorff 距离，(2) 使用比 k 最近邻更复杂的方法，(3) 改进如何将所选训练标签转化为预测。

以下是您可以使用神经网络解决此问题的几种方法：

使用简单的前馈神经网络：

• 缩放数据以适应从 (-1,-1) 到 (1,1) 的原点周围的正方形
• 用对应于其 x 和 y 坐标的两个输入来表示每个点，或者 0,0 如果 $k$th 点不存在
• 为每个点添加第三个指标输入，指示该点是否存在
• 选择隐藏层的数量和大小
• 在输出端使用大小为 10 的 softmax 层

所以每个输入示例都是一个长度为 30 的向量，其中最后一个 3*(10-$k$) 值为零时有 $k$ 集合中存在的点，输出是长度为 10 的向量，总和为 1，最大值是否对应于预测点（其位置对应于输入中的那个位置）。

使用卷积神经网络：

• 将您的飞机划分为以下网格 $n$ X $n$ 正方形，并将您的输入表示为 $n$ X $n$ 矩阵是 $k$ 如果有 $k$ 正方形中的点 ($i,j$） 和 $0$否则。希望点不会重叠，所以你有一个矩阵$1$沙 $0$s。
• 在输入矩阵上训练 CNN。你的输出形状应该是大小的softmax$n*n$，它对应于扁平化的输入形状。在相应的输出坐标处选择具有最高值的点。

CNN 可能会表现得更好，因为您的数据本质上是空间的。但是，如果两个或多个点重叠，您必须决定该怎么做。最简单的解决方案是随机选择一个，这可能取决于您的具体任务。

使用递归神经网络：

• 输入缩放 (x,y) 点的可变长度序列并输出大小为 10 的 softmax 估计

是的，就像使用 RNN 一样简单！它们可以很好地处理可变长度的输入，但它们仍然缺乏 CNN 在处理空间数据方面的优势。

注意事项：

如果使用 FNN 或 RNN，还有如何对输入数据进行排序的问题。如果您的真实数据中没有固有的顺序，那么我们不希望我们的网络对以不同顺序编码的相同数据做出不同的预测。处理此问题的一种方法是使用数据增强：使用不同的输入顺序将每个训练示例复制几次，因此希望您的网络可以学习适当的对称性。

如果你只有时间尝试一种方法，我会选择 CNN。CNN 被设计为可以很好地处理空间数据，并且输入排序没有问题。