考慮數(shù)據(jù)時(shí)效性的高效KNN算法

王軼凡

摘 要：本文在K-近鄰（KNN）算法中考慮數(shù)據(jù)時(shí)效性，在數(shù)據(jù)時(shí)效性的一系列假設(shè)下，通過蒙特卡洛模擬方法根據(jù)接受概率函數(shù)剔除訓(xùn)練集中時(shí)效性差的數(shù)據(jù).最后通過對(duì)北京市二手房成交價(jià)格數(shù)據(jù)分析，表明方法在對(duì)存在時(shí)效性的數(shù)據(jù)的問題上，在預(yù)測(cè)準(zhǔn)確率及算法時(shí)間上都有良好表現(xiàn)，具有廣泛的應(yīng)用價(jià)值.

關(guān)鍵詞：KNN算法;數(shù)據(jù)時(shí)效性;蒙特卡羅模擬

中圖分類號(hào)：TP311.13? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2019）11-0019-03

1 引言

Cover和Hart（1967）提出的KNN算法是統(tǒng)計(jì)機(jī)器學(xué)習(xí)中的經(jīng)典算法之一，是一種簡(jiǎn)單且高效的非參數(shù)分類或估計(jì)算法.KNN算法是一種“消極”學(xué)習(xí)方法，所謂的“學(xué)習(xí)”過程僅僅是將數(shù)據(jù)集存儲(chǔ)下來，在每一次的分類或回歸過程中，都需要計(jì)算帶預(yù)測(cè)樣本與所有訓(xùn)練數(shù)據(jù)的距離，計(jì)算的時(shí)間復(fù)雜度為O（D×N），其中D是樣本屬性維度，N是訓(xùn)練集樣本量.為了使算法穩(wěn)定有效的，通常情況下有D<<N，所以訓(xùn)練集樣本量N的大小對(duì)算法效率有重要的影響.對(duì)此，諸多研究者通過從全部訓(xùn)練樣本集中選擇出部分樣本，例如Hart（1968）提出的壓縮最近鄰法（Condensed Nearest Neighbor）和Gates（1972）提出的約減最近鄰法（Reduced Nearest Neighbor），他們的核心思想都是通過選擇性質(zhì)良好的訓(xùn)練樣本子集，在不失算法有效性的前提下，降低訓(xùn)練集樣本量N的大小，從而提高KNN算法的效率.

大數(shù)據(jù)時(shí)代，特別是積累了大量的時(shí)間序列數(shù)據(jù)，從而為分析研究提供了更加豐富的資源.但并不是在所有情況下，時(shí)間越長(zhǎng)，越有利.李默涵，李建中和高宏（2012）指出數(shù)據(jù)的時(shí)效性是影響數(shù)據(jù)質(zhì)量的重要因素之一，時(shí)效性差的數(shù)據(jù)對(duì)數(shù)據(jù)分析結(jié)果有許多不利影響.然而，大部分KNN算法的研究中，少有對(duì)數(shù)據(jù)的時(shí)效性的討論.大多KNN算法的研究對(duì)于有時(shí)間屬性的數(shù)據(jù)都假定在觀測(cè)時(shí)間內(nèi)，樣本的分布不隨時(shí)間變化，然而這種假設(shè)往往不符合實(shí)際.

本研究使用改進(jìn)的KNN算法，在對(duì)數(shù)據(jù)的時(shí)效性的一系列假設(shè)下，以保留時(shí)效性好的數(shù)據(jù)為依據(jù)，剔除訓(xùn)練集部分?jǐn)?shù)據(jù)，從而在提高數(shù)據(jù)分析結(jié)果準(zhǔn)確性的同時(shí)，提高KNN算法的計(jì)算效率.

本文剩余章節(jié)安排如下：第2節(jié)介紹普通的KNN算法;第3節(jié)介紹本文提出的考慮數(shù)據(jù)時(shí)效性的高效KNN算法，其中3.1小節(jié)對(duì)數(shù)據(jù)的時(shí)效性進(jìn)行一系列假設(shè)，3.2小節(jié)推導(dǎo)了訓(xùn)練集選擇的接受概率函數(shù)，3.3小節(jié)介紹具體算法;第4節(jié)對(duì)北京市二手房成交價(jià)格數(shù)據(jù)進(jìn)行實(shí)證分析，對(duì)比KNN方法與本文方法預(yù)測(cè)結(jié)果;第5節(jié)是本文的結(jié)論與討論.

2 KNN算法介紹

假設(shè)有訓(xùn)練數(shù)據(jù)集{X（i），Y（i）}i=1，…，N，其中每個(gè)樣本{X（i），Y（i）}有D維屬性X（i）=（x1（i），x2（i），…，xD（i））以及一個(gè)屬性值（或類別標(biāo)號(hào)） Y（i）=y（i）.對(duì)于待預(yù)測(cè)的樣本點(diǎn)X（i），定義其與訓(xùn)練集樣本點(diǎn){X（i），Y（i）}的屬性距離為歐式距離（也可以是任何意義上的距離）：

普通KNN算法與本文方法對(duì)比結(jié)果見表1.表1報(bào)告了普通KNN算法及本文方法對(duì)2019年6月3日的11個(gè)二手房估計(jì)結(jié)果的偏差率（偏差率=（實(shí)際值-理論值）/理論值），由于本文方法選取訓(xùn)練集基于蒙特卡洛模擬，每次選取的訓(xùn)練集可能不同，導(dǎo)致估計(jì)結(jié)果有差異，所以表1報(bào)告了3次本文方法的結(jié)果以便比較.此外，算法的計(jì)算時(shí)間也報(bào)告在表1中.

觀察表1我們由如下幾點(diǎn)發(fā)現(xiàn)：

（1）本文方法3次對(duì)11個(gè)房屋的預(yù)測(cè)中，每次的預(yù)測(cè)結(jié)果有差異但差異較小.相較于普通KNN算法，本文方法預(yù)測(cè)結(jié)果在有的房屋的預(yù)測(cè)偏差率更好，而在有的房屋的預(yù)測(cè)偏差率更差，但在預(yù)測(cè)偏差率均值上，本文方法的3次結(jié)果都優(yōu)于普通KNN方法，可以說明在考慮了數(shù)據(jù)時(shí)效性后，預(yù)測(cè)結(jié)果更準(zhǔn)確.

（2）從計(jì)算時(shí)間上看，本文方法的3次結(jié)果用時(shí)均小于普通KNN方法，低于普通KNN方法用時(shí)的一半.這是由于對(duì)訓(xùn)練集進(jìn)行選擇剔除后，訓(xùn)練集樣本量N降低，計(jì)算復(fù)雜度降低.值得一提的是，本文方法報(bào)告的計(jì)算時(shí)間不僅包括預(yù)測(cè)過程用時(shí)，還包括選擇訓(xùn)練集用時(shí).本文方法交普通KNN算法更高效.

（3）考慮房屋8和房屋11的預(yù)測(cè)結(jié)果，普通KNN方法偏差率分別為0.584和0.416，即預(yù)測(cè)值較真實(shí)值相差大約50%，預(yù)測(cè)效果很差.而本文方法對(duì)房屋8的3此預(yù)測(cè)偏差率分別為0.280，0.299，0.082，相較0.584有很大改善，對(duì)房屋11的預(yù)測(cè)偏差率分別為0.054，0.119，0.139，相較0.416有很大改善.這可能是由于本文方法剔除了時(shí)效性差的數(shù)據(jù)，使得預(yù)測(cè)結(jié)果更加準(zhǔn)確.

綜上分析，我們認(rèn)為，本文提出的考慮數(shù)據(jù)時(shí)效性的高效KNN算法能在提高數(shù)據(jù)分析結(jié)果準(zhǔn)確性的同時(shí)，降低KNN算法的計(jì)算時(shí)間.

5 討論

本文在KNN算法的基礎(chǔ)上，對(duì)數(shù)據(jù)的時(shí)效性進(jìn)行一系列假設(shè)，并在假設(shè)的基礎(chǔ)上推導(dǎo)出訓(xùn)練集接受概率函數(shù)，并提出通過蒙特卡羅模擬方法選擇新的訓(xùn)練子集，再用新的訓(xùn)練集進(jìn)行KNN算法的改進(jìn).隨后，我們將本文方法應(yīng)用到北京市西城區(qū)二手房成交價(jià)格數(shù)據(jù)的實(shí)證研究中.分析顯示，本文方法能在提高數(shù)據(jù)分析結(jié)果準(zhǔn)確性的同時(shí)，降低KNN算法的計(jì)算時(shí)間.

值得一提的是，由于本文實(shí)證旨在比較KNN算法和本文方法，屬性的選擇較為隨意，并沒有進(jìn)行詳細(xì)的影響因素分析，這導(dǎo)致預(yù)測(cè)結(jié)果的偏差率并不十分理想.如果詳細(xì)分析影響因素或使用加權(quán)KNN方法，可以得到更完美的預(yù)測(cè)結(jié)果.這值得進(jìn)一步研究.

參考文獻(xiàn)：

〔1〕Cover T M ， Hart P E . Nearest Neighbor Pattern Classification[J]. IEEE Transactions on Information Theory， 1967， 13（1）：21-27.

〔2〕Hart P E . The condensed nearest neighbor rule[J]. IEEE Trans. Inf. Theory， 1968， 14（3）：515-516.

〔3〕Gates G W . The reduced nearest neighbor rule （Corresp.）.[J]. Information Theory IEEE Transactions on， 1972， 18（3）：431-433.

〔4〕李默涵，李建中，高宏.數(shù)據(jù)時(shí)效性判定問題的求解算法[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（11）：2348-2360.

〔5〕周湘，袁文，李漢青，et al.北京市二手房?jī)r(jià)格時(shí)空演變特征[J].地球信息科學(xué)學(xué)報(bào)，2017（8）.