k-Nearest Neighbor在海量数据的情况下用什么数据结构比较好?

一、k-Nearest Neighbor在海量数据的情况下用什么数据结构比较好

k-Nearest Neighbor在海量数据的情况下，写一条数据到flat file，A_id, B_id，就这么存。针对不同的应用场景，可以做不同的优化。要实时找到有明确距离度量，甚至可以通过分块划区降低待选点的数量级的应用场景。

同时要支持待选点的实时添加和去除。

那我觉得这种情况只有系统运维需要考虑“海量”，光从KNN来说，按层次分块划区以后，直接算都可以。

那运维那边的“海量”，更是有一大堆可做的优化。比如以一个固定点代表来自一块区域的请求。全上海几千万人一起请求最近出租车，我内部只要算几万个请求来源就行了。KNN也没必要非得是最近的，我在一定区域内随机挑，期望平均距离和最小平均距离差多少是完全可控的。

KNN算法稳定性好、准确率高、简单易用，针对大数据的分类问题，它存在着如下缺点:a)对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点，而大数据的典型特点就是数据信息海量、价值密度低，这就显然出现了很大的无效计算量，在决定测试样本的类别时，该算法只计算最近邻的样本【neighbor-weighted K-nearest neighbor for unbalanced text corpus】，而大数据的另一个显著特点是涉及领域繁多、类别界限不明显，对于此类文本容易使判决结果产生偏差;c)随着信息爆炸时代的到来，各种新的事物层出不穷，出现新的类别的概率极大，而KNN算法的邻居都是已知的类别样本，也就导致了对新样本的无知或者误判。

延伸阅读：

二、改进的KNN算法—差分多层KNN (DM-KNN)算法

针对大数据的自身特点以及KNN算法的缺点，算法主要在以下几个方而进行了改进:a)构建树状分层结构，针对KNN算法计算量比较大的缺点，本文改进后的算法采用构建树状分层结构首先对高层进行比较，然后依据高层比较结果的不同，再依次对下一层次进行比较，相比直接对所有文本进行距离计算，计算量明显减少，同时提高了运算速度;b)差分比较，由于大数据具有类域交叉性的特点，该算法不是在权重比较结束后直接进行判断，而是又针对大数据的类域交叉性进行了一次差分比较，可以有效地防止最近邻和次近邻误判的情况;c)动态增加类别，由于大数据中信息的不可预知性，该算法针对最终比较结果不能判断隶属于哪个类别的情况，在算法最后可以动态增加新类别。