K-最近的邻居-有多少个参考点/特征？
K-最近的邻居-有多少个参考点/特征？
提问于 2022-11-10 02:42:37
我想使用KNN创建一个训练模型(我也会使用其他ML模型)，但我只是想知道.
我有大约6个特性，总共有60.000 (6万)个参考点(因此，我每个特性大约有10.000个参考点)。
我知道，从计算的角度来看，这并不理想(对于像KNN这样的算法)，所以我应该使用KD-树(或者KNN可以用于这几个特征/参考点)吗？因为.。如果我必须计算我的测试点和所有参考点之间的距离(例如，欧几里得距离，对于多维模型)……我可以想象这需要相当长的时间..？
我知道其他(监督) ML算法可能更有效，但KNN只是我将要使用的算法之一。
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-11-10 06:29:04
(朴素) KNN的时间复杂度为O(kdn)，其中d是你的6维数，n是点数，在你的情况下是6万。
同时，从n点构建KD树的是O(dnlogn)，随后的最近邻查找需要O(klogn)时间。这肯定要好得多:您为构建KD树牺牲了一点时间，但是以后每次KNN查找都要快得多。
所有这些都是假设您的观点以“很好”的方式分布的(更多细节请参见：https://en.wikipedia.org/wiki/K-d_tree#Degradation_in_performance_when_the_query_point_is_far_from_points_in_the_k-d_tree )。如果它们不是以“很好”的方式分发的，那么KNN在一般情况下可能是不合适的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74383602
复制相关文章
相似问题
腾讯云开发者
