一、k-Nearest Neighbor在海量數(shù)據(jù)的情況下用什么數(shù)據(jù)結(jié)構(gòu)比較好
k-Nearest Neighbor在海量數(shù)據(jù)的情況下,寫(xiě)一條數(shù)據(jù)到flat file,A_id, B_id,就這么存。針對(duì)不同的應(yīng)用場(chǎng)景,可以做不同的優(yōu)化。要實(shí)時(shí)找到有明確距離度量,甚至可以通過(guò)分塊劃區(qū)降低待選點(diǎn)的數(shù)量級(jí)的應(yīng)用場(chǎng)景。
同時(shí)要支持待選點(diǎn)的實(shí)時(shí)添加和去除。
那我覺(jué)得這種情況只有系統(tǒng)運(yùn)維需要考慮“海量”,光從KNN來(lái)說(shuō),按層次分塊劃區(qū)以后,直接算都可以。
那運(yùn)維那邊的“海量”,更是有一大堆可做的優(yōu)化。比如以一個(gè)固定點(diǎn)代表來(lái)自一塊區(qū)域的請(qǐng)求。全上海幾千萬(wàn)人一起請(qǐng)求最近出租車(chē),我內(nèi)部只要算幾萬(wàn)個(gè)請(qǐng)求來(lái)源就行了。KNN也沒(méi)必要非得是最近的,我在一定區(qū)域內(nèi)隨機(jī)挑,期望平均距離和最小平均距離差多少是完全可控的。
KNN算法穩(wěn)定性好、準(zhǔn)確率高、簡(jiǎn)單易用,針對(duì)大數(shù)據(jù)的分類(lèi)問(wèn)題,它存在著如下缺點(diǎn):a)對(duì)每一個(gè)待分類(lèi)的文本都要計(jì)算它到全體已知樣本的距離,才能求得它的K個(gè)最近鄰點(diǎn),而大數(shù)據(jù)的典型特點(diǎn)就是數(shù)據(jù)信息海量、價(jià)值密度低,這就顯然出現(xiàn)了很大的無(wú)效計(jì)算量,在決定測(cè)試樣本的類(lèi)別時(shí),該算法只計(jì)算最近鄰的樣本【neighbor-weighted K-nearest neighbor for unbalanced text corpus】,而大數(shù)據(jù)的另一個(gè)顯著特點(diǎn)是涉及領(lǐng)域繁多、類(lèi)別界限不明顯,對(duì)于此類(lèi)文本容易使判決結(jié)果產(chǎn)生偏差;c)隨著信息爆炸時(shí)代的到來(lái),各種新的事物層出不窮,出現(xiàn)新的類(lèi)別的概率極大,而KNN算法的鄰居都是已知的類(lèi)別樣本,也就導(dǎo)致了對(duì)新樣本的無(wú)知或者誤判。
延伸閱讀:
二、改進(jìn)的KNN算法—差分多層KNN (DM-KNN)算法
針對(duì)大數(shù)據(jù)的自身特點(diǎn)以及KNN算法的缺點(diǎn),算法主要在以下幾個(gè)方而進(jìn)行了改進(jìn):a)構(gòu)建樹(shù)狀分層結(jié)構(gòu),針對(duì)KNN算法計(jì)算量比較大的缺點(diǎn),本文改進(jìn)后的算法采用構(gòu)建樹(shù)狀分層結(jié)構(gòu)首先對(duì)高層進(jìn)行比較,然后依據(jù)高層比較結(jié)果的不同,再依次對(duì)下一層次進(jìn)行比較,相比直接對(duì)所有文本進(jìn)行距離計(jì)算,計(jì)算量明顯減少,同時(shí)提高了運(yùn)算速度;b)差分比較,由于大數(shù)據(jù)具有類(lèi)域交叉性的特點(diǎn),該算法不是在權(quán)重比較結(jié)束后直接進(jìn)行判斷,而是又針對(duì)大數(shù)據(jù)的類(lèi)域交叉性進(jìn)行了一次差分比較,可以有效地防止最近鄰和次近鄰誤判的情況;c)動(dòng)態(tài)增加類(lèi)別,由于大數(shù)據(jù)中信息的不可預(yù)知性,該算法針對(duì)最終比較結(jié)果不能判斷隸屬于哪個(gè)類(lèi)別的情況,在算法最后可以動(dòng)態(tài)增加新類(lèi)別。