一、k-Nearest Neighbor在海量數(shù)據(jù)的情況下用什么數(shù)據(jù)結(jié)構(gòu)比較好

k-Nearest Neighbor在海量數(shù)據(jù)的情況下，寫一條數(shù)據(jù)到flat file，A_id, B_id，就這么存。針對不同的應(yīng)用場景，可以做不同的優(yōu)化。要實(shí)時找到有明確距離度量，甚至可以通過分塊劃區(qū)降低待選點(diǎn)的數(shù)量級的應(yīng)用場景。

同時要支持待選點(diǎn)的實(shí)時添加和去除。

那我覺得這種情況只有系統(tǒng)運(yùn)維需要考慮“海量”，光從KNN來說，按層次分塊劃區(qū)以后，直接算都可以。

那運(yùn)維那邊的“海量”，更是有一大堆可做的優(yōu)化。比如以一個固定點(diǎn)代表來自一塊區(qū)域的請求。全上海幾千萬人一起請求最近出租車，我內(nèi)部只要算幾萬個請求來源就行了。KNN也沒必要非得是最近的，我在一定區(qū)域內(nèi)隨機(jī)挑，期望平均距離和最小平均距離差多少是完全可控的。

KNN算法穩(wěn)定性好、準(zhǔn)確率高、簡單易用，針對大數(shù)據(jù)的分類問題，它存在著如下缺點(diǎn):a)對每一個待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個最近鄰點(diǎn)，而大數(shù)據(jù)的典型特點(diǎn)就是數(shù)據(jù)信息海量、價值密度低，這就顯然出現(xiàn)了很大的無效計(jì)算量，在決定測試樣本的類別時，該算法只計(jì)算最近鄰的樣本【neighbor-weighted K-nearest neighbor for unbalanced text corpus】，而大數(shù)據(jù)的另一個顯著特點(diǎn)是涉及領(lǐng)域繁多、類別界限不明顯，對于此類文本容易使判決結(jié)果產(chǎn)生偏差;c)隨著信息爆炸時代的到來，各種新的事物層出不窮，出現(xiàn)新的類別的概率極大，而KNN算法的鄰居都是已知的類別樣本，也就導(dǎo)致了對新樣本的無知或者誤判。

延伸閱讀：

二、改進(jìn)的KNN算法—差分多層KNN (DM-KNN)算法

針對大數(shù)據(jù)的自身特點(diǎn)以及KNN算法的缺點(diǎn)，算法主要在以下幾個方而進(jìn)行了改進(jìn):a)構(gòu)建樹狀分層結(jié)構(gòu)，針對KNN算法計(jì)算量比較大的缺點(diǎn)，本文改進(jìn)后的算法采用構(gòu)建樹狀分層結(jié)構(gòu)首先對高層進(jìn)行比較，然后依據(jù)高層比較結(jié)果的不同，再依次對下一層次進(jìn)行比較，相比直接對所有文本進(jìn)行距離計(jì)算，計(jì)算量明顯減少，同時提高了運(yùn)算速度;b)差分比較，由于大數(shù)據(jù)具有類域交叉性的特點(diǎn)，該算法不是在權(quán)重比較結(jié)束后直接進(jìn)行判斷，而是又針對大數(shù)據(jù)的類域交叉性進(jìn)行了一次差分比較，可以有效地防止最近鄰和次近鄰誤判的情況;c)動態(tài)增加類別，由于大數(shù)據(jù)中信息的不可預(yù)知性，該算法針對最終比較結(jié)果不能判斷隸屬于哪個類別的情況，在算法最后可以動態(tài)增加新類別。