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

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

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

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

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