一洽议、算法簡(jiǎn)介
K最近鄰(kNN指黎，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡(jiǎn)單的方法之一芯砸。K近鄰的意思是每個(gè)樣本都可以用它最接近的k個(gè)鄰居來(lái)代表硼端。
kNN算法的核心思想是如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別并淋，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性珍昨。因此KNN是通過(guò)測(cè)量不同特征值之間的距離進(jìn)行分類县耽。
KNN輸入基于實(shí)例的學(xué)習(xí)，屬于懶惰學(xué)習(xí)镣典，即它沒(méi)有顯式的學(xué)習(xí)過(guò)程兔毙，也就是說(shuō)沒(méi)有訓(xùn)練階段，數(shù)據(jù)集事先已有了分類和特征值兄春，待收到新樣本后直接進(jìn)行處理.
二澎剥、算法實(shí)現(xiàn)步驟
1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；
2）按照距離的遞增關(guān)系進(jìn)行排序赶舆；
3）選取距離最小的K個(gè)點(diǎn)哑姚；
4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率；
5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類
三芜茵、注意事項(xiàng)
1叙量、K值的選取
K值的選取非常重要。當(dāng)K的取值過(guò)小時(shí)九串，一旦有噪聲成分存在將會(huì)對(duì)預(yù)測(cè)產(chǎn)生比較大影響绞佩；如果K的值取的過(guò)大，就相當(dāng)于用較大鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)猪钮，學(xué)習(xí)的近似誤差會(huì)增大征炼。
常用的取k方法是從k=1開(kāi)始，使用檢驗(yàn)集估計(jì)分類器的誤差率躬贡。重復(fù)該過(guò)程谆奥，每次K增值1，允許增加一個(gè)近鄰拂玻。選取產(chǎn)生最小誤差率的K酸些。一般k的取值不超過(guò)20宰译，上限是n的開(kāi)方，隨著數(shù)據(jù)集的增大魄懂，K的值也要增大沿侈。此外，K一般取奇數(shù)來(lái)減少平局的產(chǎn)生市栗。
2缀拭、距離的選取
常用的是歐式距離。兩個(gè)樣本點(diǎn)之間歐式距離的平方是樣本點(diǎn)各個(gè)維度差的平方和填帽。
四蛛淋、算法評(píng)價(jià)
優(yōu)點(diǎn)
1.簡(jiǎn)單，易于理解篡腌，易于實(shí)現(xiàn)褐荷，無(wú)需估計(jì)參數(shù)，無(wú)需訓(xùn)練嘹悼；
2. 適合對(duì)稀有事件進(jìn)行分類叛甫；
3.特別適合于多分類問(wèn)題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽)， kNN比SVM的表現(xiàn)要好杨伙。
缺點(diǎn)
1.該算法在分類時(shí)有個(gè)主要的不足是其监，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大限匣，而其他類樣本容量很小時(shí)棠赛，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)膛腐。 該算法只計(jì)算“最近的”鄰居樣本睛约，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本哲身，或者這類樣本很靠近目標(biāo)樣本辩涝。無(wú)論怎樣，數(shù)量并不能影響運(yùn)行結(jié)果勘天。
2.該方法的另一個(gè)不足之處是計(jì)算量較大怔揩，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)脯丝。
3.可理解性差商膊，無(wú)法給出像決策樹(shù)那樣的規(guī)則。
五宠进、Python實(shí)現(xiàn)knn算法
import numpy as np
import matplotlib.pyplot as plt
import operator
#類的封裝
class KNN(object):
? ? def __init__(self, k=3):
? ? ? ? self.k = k
? ? def fit(self,x,y):
? ? ? ? self.x = x
? ? ? ? self.y = y
#計(jì)算距離的平方
? ? def _square_distance(self,v1,v2):
? ? ? ? return np.sum(np.square(v1-v2))
#投票
? ? def _vote(self,ys):
? ? ? ? ys_unique = np.unique(ys)
? ? ? ? vote_dict = {}
? ? ? ? for y in ys:
? ? ? ? ? ? if y not in vote_dict.keys():
? ? ? ? ? ? ? ? vote_dict[y] = 1
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? vote_dict[y] += 1
? ? ? ? sorted_vote_dict = sorted(vote_dict.items(), key=operator.itemgetter(1),reverse=True)
? ? ? ? return sorted_vote_dict[0][0]
#建立模型
? ? def predict(self,x):
? ? ? ? y_pred = []
? ? ? ? for i in range(len(x)):
? ? ? ? ? ? dist_arr = [self._square_distance(x[i],self.x[j])for j in range(len(self.x))]
? ? ? ? ? ? sorted_index = np.argsort(dist_arr)
? ? ? ? ? ? top_k_index = sorted_index[:self.k]
? ? ? ? ? ? y_pred.append(self._vote(ys=self.y[top_k_index]))
? ? ? ? return np.array(y_pred)
#模型評(píng)分
? ? def score(self,y_true=None, y_pred =None):
? ? ? ? if y_true is None or y_pred is None:
? ? ? ? ? ? y_pred = self.predict(self.x)
? ? ? ? ? ? y_true = self.y
? ? ? ? score = 0
? ? ? ? for i in range(len(y_true)):
? ? ? ? ? ? if y_true[i] == y_pred[i]:
? ? ? ? ? ? ? ? score += 1
? ? ? ? score /= len(y_true)
? ? ? ? return score
#生成數(shù)據(jù)
np.random.seed(666)
data_size_1 = 300? #生成兩組數(shù)據(jù)晕拆，第一組樣本點(diǎn)為300
x1_1 = np.random.normal(loc=5, scale=1, size=data_size_1)#樣本點(diǎn)的一個(gè)維度
x2_1 = np.random.normal(loc=4, scale=1, size=data_size_1)#樣本點(diǎn)的另一個(gè)維度
y_1 = [0 for i in range(data_size_1)]
data_size_2 = 400? #
x1_2 = np.random.normal(loc=10, scale=2, size=data_size_2)
x2_2 = np.random.normal(loc=8, scale=2, size=data_size_2)
y_2 = [1 for j in range(data_size_2)]
#數(shù)據(jù)的拼接
x1 = np.concatenate((x1_1, x1_2), axis=0)
x2 = np.concatenate((x2_1, x2_2), axis=0)
x = np.hstack((x1.reshape(-1, 1), x2.reshape(-1, 1)))
y = np.concatenate((y_1, y_2), axis=0)
#數(shù)據(jù)洗牌
data_size_all = data_size_2+data_size_1
shuffled_index = np.random.permutation(data_size_all)
x = x[shuffled_index]
y = y[shuffled_index]
#切分訓(xùn)練集和測(cè)試集
split_index = int(data_size_all * 0.7)
x_train = x[:split_index]
y_train = y[:split_index]
x_test = x[split_index:]
y_test = y[split_index:]
#數(shù)據(jù)微化
x_train = (x_train - np.min(x_train, axis=0))/(np.max(x_train, axis=0)-np.min(x_train,axis=0))
x_test = (x_test - np.min(x_test, axis=0))/(np.max(x_test, axis=0)-np.min(x_test,axis=0))
#
clf = KNN(k=3)
clf.fit(x_train,y_train)
score_train = clf.score()
print('Train Accuracy: {:.3}'.format(score_train))
y_test_pred = clf.predict(x_test)
print('Test Accuracy:{:.3}'.format(clf.score(y_test,y_test_pred)))
輸出結(jié)果為:
Train Accuracy: 0.988
Test Accuracy:0.991
#代碼實(shí)現(xiàn)主要參考自u(píng)p主:rocktsunami
