本文來自同步博客刘莹。
P.S. 不知道簡書怎么顯示數(shù)學(xué)公式以及更好的排版內(nèi)容阎毅。所以如果覺得文章下面格式亂的話請自行跳轉(zhuǎn)到上述鏈接。后續(xù)我將不再對數(shù)學(xué)公式進行截圖点弯，畢竟行內(nèi)公式截圖的話排版會很亂扇调。看原博客地址會有更好的體驗抢肛。
本文內(nèi)容介紹機器學(xué)習(xí)的K近鄰算法狼钮，用它處理分類問題。分類問題的目標(biāo)是利用采集到的已經(jīng)經(jīng)過分類處理的數(shù)據(jù)來預(yù)測新數(shù)據(jù)屬于何種類別捡絮。
K近鄰算法
K近鄰算法對給定的某個新數(shù)據(jù)熬芜，讓它與采集到的樣本數(shù)據(jù)點分別進行比較福稳，從中選擇最相似的K個點，然后統(tǒng)計這K個點中出現(xiàn)的各個類別的頻數(shù)鼓拧，并判定頻數(shù)最高的類別作為新數(shù)據(jù)所屬的類別季俩。
這里有個問題是如何判定樣本數(shù)據(jù)與新數(shù)據(jù)是否相似。常用的一種計算方法叫歐幾里得距離店归。
歐幾里得距離（Euclidean Distance）
假設(shè)有兩個數(shù)據(jù)分別是：- X = (x\_1,x\_2,...,x\_n) -和- Y = (y\_1,y\_2,...,y\_n) -赂韵。則-X-與-Y-的距離為：
D = \sqrt{\sum\_{i=1}^{n}(x\_i-y\_i)^2}
用Python實現(xiàn)這個式子代碼如下：
def euclidean_distance(x, y):
if len(x) != len(y):
warnings.warn('Input error')
return sqrt( sum( [(x[i] - y[i])**2 for i in range(0, len(x))] ) )
print(euclidean_distance([1,2,3], [2,4,5]))
NumPy提供則可以用下面方法計算兩個ndarray的距離：
np.linalg.norm(np.array([1,2,3]) - np.array([2,4,5]))
實現(xiàn)K近鄰算法
接下來依照上面描述的算法原理實現(xiàn)K近鄰算法祭示。先定義一下輸入數(shù)據(jù)的格式：
#二維測試數(shù)據(jù)的格式
dataset = {'k': [[1,2],[2,3],[3,1]], 'r':[[6,5],[7,7],[8,6]]}
new_features = [5,7]
我們假定樣本數(shù)據(jù)的結(jié)構(gòu)如dataset為一個字典類型的數(shù)據(jù)质涛，字典的元素的關(guān)鍵字為類型名稱汇陆，元素值為一個包含該類型所有樣本點的列表。新數(shù)據(jù)為一個數(shù)據(jù)點阅羹。
所以K近鄰算法的實現(xiàn)如下：
# KNN實現(xiàn)
def k_nearest_neighbors(data, predict, k=3):
if len(data) >= k:
warnings.warn('K less than total voting groups')
# 計算距離
distances = []
for group in data:
for features in data[group]:
#distance = euclidean_distance(features, predict)
distance = np.linalg.norm(np.array(features)-np.array(predict))
distances.append([distance, group])
# 排序后取前k項數(shù)據(jù)類別構(gòu)成新數(shù)組
votes = [i[1] for i in sorted(distances)[:k]]
# 統(tǒng)計數(shù)組中頻數(shù)最高的類別
vote_result = Counter(votes).most_common(1)[0][0]
return vote_result
# 調(diào)用KNN
result = k_nearest_neighbors(dataset, new_features, k=3)
print(result)
使用真實數(shù)據(jù)測試
在UCI網(wǎng)站的機器學(xué)習(xí)數(shù)據(jù)庫中可以找到Breast Cancer Wisconsin(Original)的真實統(tǒng)計數(shù)據(jù)教寂。數(shù)據(jù)可以從這個鏈接下載，數(shù)據(jù)的描述可以看這個鏈接导梆。
看到數(shù)據(jù)描述中提到了數(shù)據(jù)每一列的定義如下：
這份數(shù)據(jù)的預(yù)測目標(biāo)是判斷給定特征數(shù)據(jù)對應(yīng)的乳癌情況迂烁，2表示良性、4表示惡性藏斩。
根據(jù)描述我們先處理一下下載到的數(shù)據(jù)却盘，給它的每一列加上個列名窜觉。這樣在Python里面就可以把它當(dāng)成一個CSV文件處理。我這里把它保存到了一個名為breast-cancer-wisconsin.data的文件里旬陡。形狀如下：
數(shù)據(jù)里面還有一些統(tǒng)計不到的數(shù)據(jù)驶睦，用英文問號?表示匿醒。還有一個很奇怪的現(xiàn)象是數(shù)據(jù)讀取進來后有些數(shù)字會被處理成字符串類型廉羔，如'1'這樣的數(shù)據(jù)。這些都需要我們提前處理一下孩饼。
df = pd.read_csv('./dataset/breast-cancer-wisconsin.data')
# 處理問號
df.replace('?', -99999, inplace=True)
# id字段不應(yīng)該當(dāng)成一個統(tǒng)計特征字段镀娶，因此去除該列的內(nèi)容
df.drop(['id'], 1, inplace=True)
# 源數(shù)據(jù)有部分?jǐn)?shù)據(jù)是字符串揪罕，如'1'，這對我們的模型有影響轩娶，所以整理一下類型
# 用列表存放數(shù)據(jù)
full_data = df.astype(float).values.tolist()
random.shuffle(full_data) # 洗亂數(shù)據(jù)
接下來生成訓(xùn)練數(shù)據(jù)集和統(tǒng)計數(shù)據(jù)集坎怪，代碼如下：
# 生成訓(xùn)練數(shù)據(jù)集和統(tǒng)計數(shù)據(jù)集
test_size = 0.2
train_set = {2:[], 4:[]} # 訓(xùn)練集搅窿，占80%
test_set = {2:[], 4:[]} # 統(tǒng)計集嘁酿，占20%
train_data = full_data[:-int(test_size*len(full_data))]
test_data = full_data[-int(test_size*len(full_data)):]
for i in train_data:
train_set[i[-1]].append(i[:-1])
for i in test_data:
test_set[i[-1]].append(i[:-1])
最后男应，利用上述KNN函數(shù)統(tǒng)計測試數(shù)據(jù)的準(zhǔn)確性闹司。
correct = 0
total = 0
for group in test_set:
for data in test_set[group]:
vote = k_nearest_neighbors(train_set, data, k=5)
if group == vote:
correct += 1
total += 1
# 打印結(jié)果
print('correct: ', correct)
print('total: ', total)
print('Accuracy: ', correct/total)
完整代碼請查看github鏈接。
sklearn的K近鄰算法
同樣需要先處理一下數(shù)據(jù)并生成符合sklearn的輸入格式的數(shù)據(jù)集游桩。
from sklearn import model_selection
# 讀取乳癌統(tǒng)計數(shù)據(jù)
df = pd.read_csv('./dataset/breast-cancer-wisconsin.data')
# 處理問號
df.replace('?', -99999, inplace=True)
# 因為ID字段與分類無關(guān)牲迫，所以去除他先，稍后我們看一下它的影響
df.drop(['id'], 1, inplace=True)
df = df.astype(float)
# 生成數(shù)據(jù)集
X = np.array(df.drop(['class'], 1))
y = np.array(df['class'])
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y, test_size=0.2)
然后生成KNN模型對象借卧，用數(shù)據(jù)訓(xùn)練模型，評估模型準(zhǔn)確性铐刘。
from sklearn import neighbors
# 構(gòu)建模型與訓(xùn)練
clf = neighbors.KNeighborsClassifier()
clf.fit(X_train, y_train)
# 計算精確度
accuracy = clf.score(X_test, y_test)
print('Accuracy: ', accuracy)
# 預(yù)測我們自己構(gòu)造的數(shù)據(jù)屬于哪個類型
example_measures = np.array([[4,2,1,1,1,2,3,2,1],[2,3,4,4,1,2,3,4,1]])
prediction = clf.predict(example_measures)
print('Predict resuct: ', prediction)
完整代碼請查看github鏈接陪每。
