基于訓(xùn)練集聚類(lèi)的KNN算法及其應(yīng)用研究.pdf

1、本文主要研究K最近鄰（K-Nearest Neighbor，KNN）算法及其應(yīng)用。KNN算法是一種經(jīng)典的分類(lèi)算法，該算法需要計(jì)算待測(cè)樣本與每個(gè)訓(xùn)練集樣本的相似性，相似性通常用歐氏距離表示，然而在大數(shù)據(jù)的背景下，KNN算法將會(huì)產(chǎn)生巨大的計(jì)算量，使得算法的效率大打折扣，而且KNN算法中， k值的選取對(duì)分類(lèi)結(jié)果也有一定的影響，一般需要做多次實(shí)驗(yàn)確定，因此針對(duì)KNN算法的以上缺陷，本文做了以下一些主要工作。
　　第一，通過(guò)改進(jìn)的局部線性嵌

2、入算法（Locally Linear Embedding,LLE）對(duì)高維數(shù)據(jù)降維，再結(jié)合模糊C均值（Fuzzy c-means，F(xiàn)CM）算法對(duì)訓(xùn)練集聚類(lèi)，從距離待測(cè)樣本最近的幾個(gè)聚類(lèi)包含的數(shù)據(jù)中，通過(guò)計(jì)算找到k最近鄰，這樣就不需要計(jì)算訓(xùn)練集的所有樣本與待測(cè)樣本的距離，只計(jì)算一小部分即可，然后設(shè)計(jì)了一種基于距離為k最近鄰賦予權(quán)值的方法，削弱k值的選取對(duì)分類(lèi)結(jié)果的影響。第三章將KNN算法與數(shù)據(jù)降維、FCM算法、基于距離加權(quán)相結(jié)合，提出了基于

3、訓(xùn)練集聚類(lèi)的距離加權(quán)KNN算法，通過(guò)對(duì)模擬數(shù)據(jù)和UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，將新算法與KNN算法進(jìn)行對(duì)比，驗(yàn)證了新算法的有效性。
　　第二，數(shù)據(jù)的分布通常是不均勻的，對(duì)于存在類(lèi)偏斜的訓(xùn)練集數(shù)據(jù)，第四章提出了基于訓(xùn)練集聚類(lèi)的密度加權(quán)KNN算法，通過(guò)改進(jìn)的LLE算法對(duì)訓(xùn)練集降維，運(yùn)用K-means算法對(duì)訓(xùn)練集進(jìn)行聚類(lèi)操作，在找到待測(cè)樣本的k最近鄰之后，用設(shè)計(jì)的一種基于密度賦予k最近鄰權(quán)重的方法進(jìn)行加權(quán)操作，根據(jù)權(quán)重的大小判斷待測(cè)樣本的類(lèi)別，

4、通過(guò)對(duì)模擬數(shù)據(jù)和UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，將新算法與KNN算法、基于訓(xùn)練集聚類(lèi)的距離加權(quán)KNN算法進(jìn)行對(duì)比，驗(yàn)證了新算法對(duì)于分布不均勻的數(shù)據(jù)有著更高的分類(lèi)準(zhǔn)確率。
　　第三，將上述兩種改進(jìn)的KNN算法應(yīng)用于入侵檢測(cè)數(shù)據(jù)集KDD Cup1999 Data，通過(guò)與KNN算法對(duì)比，驗(yàn)證了改進(jìn)算法的準(zhǔn)確率更高。除此之外，對(duì)兩種改進(jìn)的KNN算法進(jìn)行對(duì)比分析，基于訓(xùn)練集聚類(lèi)的密度加權(quán)KNN算法在處理分布不均勻的數(shù)據(jù)時(shí)有著更好的效果。
　　最