我正在寻找至少有个共同特征的向量对。$L$

这只是二元特征向量的内积。当内积大于时，该对将至少有个共同元素。这应该是一个相对较快的计算 - 至少比欧几里得距离更快，这对于这些数据来说是浪费和缓慢的。因为你规定你正在寻找对，这本质上意味着你必须做计算来比较每个向量。$L-1$$L$$\binom{N}{2}$

找到靠近的点确实是一个聚类问题。但我熟悉的聚类算法的第一步是计算成对距离或相似度。我确信有人已经开发出更有效的替代方案。关于术语的一点：至少有个共同邻居被表述为相似性，而不是距离！在这种情况下，内积是未归一化的余弦相似度。$L$

您可以通过仅在观察的特征向量（在这种情况下与范数相同）的总和大于时执行内积计算来使其更易于处理，因为该二进制特征向量是不可能的与另一个二进制特征向量有一个内积，当这个总和小于时，它将满足我的标准。显然，计算这些总和只是复杂度，因此 i 是降低内积步骤幅度的一种廉价方法。$L-1$$L$$O(N)$

但是缩小这个问题范围的经典方法是做额外的预过滤。您是否对某个不常见的功能取值为 1 时特别感兴趣？如果是这样，只对那些特征向量执行计算。

或者也许你可以从重新构建你的问题中受益。例如，众所周知，采样具有很好的特性。推论统计在这个想法上发展到相当深的程度。所以也许分析整个数据集是不可行的，但检查一个小样本是完全可行的。我不知道你想回答什么问题，但如果你仔细设计你的实验，你可能只看几千个观察结果，剩下的数据足够多用于验证目的。

经过一些额外的思考，我有一种强烈的预感，您正在使用的数据是某种图表。由几个连通分量组成是非常合理分解为一组图，并带来降低数据维度的愉快副作用。即使该图只有两个大小大致相同的连通分量，这也意味着您的成对比较具有大约的总成本！$G$$G$$G$$O(N^2)$$\frac{1}{4}$

如果图形是对称的，以下观察可能会有所帮助：

1. 将图的拉普拉斯算子定义为，其中是度数对角矩阵（每个特征向量的总和），是邻接矩阵（特征向量堆叠成矩阵）。$P=D-A$$D$$A$
2. 的特征值出现的次数的连通分量的数量。将图分解为其连接的组件并单独使用这些组件将产生减少数据维度的副作用；计算您感兴趣的数量会更容易。但是对于一百万个顶点计算特征分解将是昂贵的......$0$$P$$G$
3. （完全置换后）是的连通分量的拉普拉斯算子的块对角矩阵。$P$$G$
4. $P$是半正定的。这几乎肯定是有用的。
5. 的代数连通性的第二小的特征值的值。这告诉你的连通性如何。也许这将回答您感兴趣的一些问题：具有共同特征的向量。谱图理论更详细地发展了这个想法。$G$$P$$G$

“这是一个 SNA 问题吗？” 我不知道。在一个应用程序中，功能描述了行为，我们希望将具有相似行为的人联系起来。这是否使这成为 SNA 问题？

如果您有一个将人与行为联系起来的二分图，您可以将其视为从属网络，其中人是行，行为是列。如果您想通过人们的共同行为将人们与人们联系起来，您可以计算。是人们共同行为的数量。显然，的顶点集回答了你的问题。$B$$BB^T=A$$A_{ij}$$A_{ij}\ge L$

看起来您正在寻找的方法是 minhash 签名和 Locality Sensitive Hashing (LSH) 的组合；Mining Massive Datasets的（免费提供）pdf在第 3 章中详细描述了这种方法（和其他相似性度量），但简要说明：

minhash签名是原始矩阵的浓缩表示，它是通过将一些n个哈希函数应用于特征而构造的，从而减少每次观察的特征数量。这会减少数据的大小，但是您可能会注意到这仍然会给您留下的问题。$O(N^2)$

为了解决这个问题，MMDS 建议，如果您只想找到高于某个相似度阈值的配对（这似乎适用于您的情况），那么您可以只关注那些最有可能相似的配对 - 这种方法称为Locality Sensitive Hashing，在第 3.4 节中，他们介绍了如何将 minhash 签名方法与 LSH 相结合的示例。

除了课文，Coursera 课程也有同名讲座。

关于寻找在时空块中相遇的人：
将空间分成块（城市块、平方公里等），将时间分成块。如果人们见面，他们很有可能会在同一个街区内见面。 所以在每个块中运行 NN。运行时间和错误率当然取决于块的大小和形状（也取决于你可以并行化/ MapReduce 的内容），但是你有参数可以使用——工程，而不是开放的。$Nspace$$Ntime$
$O( N^2 )$

另请参阅：datascience.stackexchange 上
的最近邻搜索搜索非常高维数据

成对的.py：

使用 Python Gensim 库和标准库中的 heapq 使用 TF-IDF 和余弦距离在任意大量文档之间进行大规模快速和可扩展的成对比较。

倒字典！将点表示为，对应于非零值的键（即特征保持为真）。元素的平均存储大小为。实际上，我只需要个字符串来存储特征和个浮点数来保存值。$x$$feat_1:value_1, feat_{101}:value_{101}$$K$$K$$K$

对于每个特征，构建一个包含共享该特征的索引的字典。希望这个数字不会太大（如果您有一个由所有索引共享的功能，那么这种方法就被破坏了，您可以在此处停止阅读）。

这本字典看起来像：。如果我想提高速度并节省空间，我什至可以放弃仅在一个元素中找到的特征（此处为：），因为它们不会产生紧密的对。该字典内置在操作中。$feat_1 : \{1,101,202\}, feat_2 : \{7,202\},feat_3 : \{202\}...feat_M:\{3,45,6\}$$feat_3$$O(NK)$

现在，当您想要评估元素共享至少一个特征的索引列表。您知道所有其他元素都与相去甚远（它们甚至不共享一个特征！）。如果“每个特征的元素”的平均数量很低（称为），则您不再需要处于中。$x$$x$$x$$P$$O(N^2)$

现在，如果和也表示为字典，则还有另一个重大改进，因为或可以在操作中迭代和$x$$y$$d(x,y)$$<x,y>$$x$$y$$O(K)$

您最终的复杂性是而不是天真的初始方法。$O(NPK)$$O(MN^2)$

我应用这种方法在大型文本集上实现了一个 KNN（训练：2 000 000 行，测试 35 000 行，特征数：10 000，每个元素的平均特征数：20），运行大约一个小时。 .