一、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)動態增加類別,由于大數據中信息的不可預知性,該算法針對最終比較結果不能判斷隸屬于哪個類別的情況,在算法最后可以動態增加新類別。