如何找到一对(或三个或更多)的对象，在一起是最相似的给定标准?

Question

对象将由各种数据组成，但我们将只使用数字数据进行算法，这应该会简化一些事情。

我将用一个例子来解释我的问题。假设我们有一个200多名篮球运动员的名单和他们的平均比赛数据。假设我想找到一个与其他玩家属性最相似的玩家。这在合理的时间内是可行的。

我正在努力弄清楚的是如何找到两个当球员组合在一起时，他们的数据更像某个单一的篮球运动员，而不是所有其他篮球运动员组合。例如:

我正在寻找一对球员，当组合时平均统计:

• 分:21.1
• 板:11.1
• 助攻:17.3
• 投篮命中率:44%
• 等。

算法应该返回球员A和球员B比其他任何两个球员更接近这些平均数据。

这是否可行，特别是考虑到每个篮球运动员有9到11个不同的数值需要考虑?篮球运动员的名单至少有200人。最重要的是，是否有可能将这个问题扩展到不仅寻找成对的玩家，还寻找三人或更多的玩家?

我正在做一个个人项目，希望你能告诉我如何解决这个问题。谢谢你！

Answer 1

这是一个建议的算法。

称M为你想要接近的理想平均值。

对于每个玩家p:

• 查找玩家Q = Q(P)使得(P+Q)/2最接近M;
• 注d(P) (P+Q)/2与M的距离

使d(p)最小的返回对(p, Q(p))

这个算法是有效的，只要给定一个玩家p，"找到玩家Q"的操作使(p +Q)/2最接近M"是有效的。

注意下面两个操作是等价的:

• 找到玩家Q使(P+Q)/2最接近M;
• 找到最接近M + (M - P)的玩家Q。

从几何上讲，很容易理解这个等价。点R = M+(M-P)在点M周围的中心对称中是P的对称;换句话说，R是使M正好位于段PR中间的点。

现在，给定点R = M + (M - p)，操作"找到离R最近的玩家Q";如果将点存储在专门设计的数据结构中，则可以有效地完成此操作。k-d树就是这样一种数据结构。

下面是一段使用scikit-learn的sklearn.neighbors.KDTree的python代码:

from sklearn.neighbors import KDTree
from numpy import argmin
# X should be numpy array with
#   one row per player
#   one column per feature
def find_bestavg_pair(X, m):
tree = KDTree(X, leaf_size=5)    # KDTree makes it easy to find nearest neighbour of a point
# REMOVE leaf_size=5 IF NUMBER OF PLAYERS IS LARGE
distances, best_indices = tree.query(m + (m-X), k=1)
i = argmin(distances)
return i, best_indices[i].item()

随机数据的检验:

from numpy.random import random
n_players = 100
n_features = 4
players = random((n_players, n_features))
m = random(n_features)
print('Players:')
print(players)
print('Ideal average:')
print('    ', m)
i_p, i_q = find_bestavg_pair(players, m)
p, q = players[i_p], players[i_q]
print()
print('Found best pair:')
print('    ', p)
print('    ', q)
print('Average:')
print('    ', (p+q)/2)
print('Distance from average to ideal average:')
print('    ', norm(m - (p+q)/2))

输出:

Players:
[[0.92374607 0.17773757 0.86935844 0.23778054]
[0.66040649 0.24189426 0.28202681 0.29389967]
[0.5913366  0.67835115 0.68202081 0.34955092]
...
[0.89292432 0.25801491 0.4732747  0.39460182]
[0.97629877 0.32180046 0.32901506 0.64657499]]
Ideal average:
[0.8075199  0.41172765 0.94341118 0.87773564]
Found best pair:
[0.9056168  0.72582579 0.97190164 0.77675535]
[0.56901592 0.06824099 0.97213458 0.81913477]
Average:
[0.73731636 0.39703339 0.97201811 0.79794506]
Distance from average to ideal average:
0.11103762079607322