作者：數據取經團——Monke
數據取經團（公眾號：zlx19930503）
專注R、Python數據分析挖掘、可視化、機器學習
走了很多彎路，看了很多風景，才發現，想要好好學算法，還是要一行一行敲代碼，於是有了這個系列。
這個系列按照機器學習實戰的章節來寫，由於市面上已經有很多同類的文章，一般以介紹算法，貼代碼，舉例子為主，個人讀下來，覺得對於實現的代碼還是不能有很好的理解，所有有了這個系列。要寫這個系列還有三個原因：
實戰的代碼是Python2的，有一些用法已經在python3中不支持了，以後的系列都以pyhton3完成，遇到python2不支持的坑，會進行一下對比
有一些初級的函數在初學階段是需要積累的，孤立的去記憶比較費時費力，所以一邊學算法的實現，一邊把遇到的一些函數的用法記錄下來~
遇到有趣的pythonic的表達，記錄分享出來，做知識積累。
鄰近算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。平常生活中我們都會下意識的運用到我們的判斷中，比如富人區和窮人區，判斷一個人是富人還是窮人根據他的朋友的判斷，就是運用了kNN的思想。
KNN是通過測量不同特徵值之間的距離進行分類。它的的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。K通常是不大於20的整數。KNN算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
在KNN中，通過計算對象間距離來作為各個對象之間的非相似性指標，避免了對象之間的匹配問題，在這裡距離一般使用歐氏距離：
或曼哈頓距離
曼哈頓距離歐式距離和曼哈頓距離都是閔可夫斯基距離(Minkowski Distance)$p=2$和$p=1$的特例，定義為：
閔可夫斯基距離本節主要參考劉建平Pinard的博文K近鄰法(KNN)原理小結，劉建平Pinard的博文對每個算法有很深刻的見解，一般在看不懂李航的《統計學習方法》的時候，去看劉大大的博客會有豁然開朗的感覺。他博文中提到scikit-learn裡只使用了蠻力實現(brute-force)，KD樹實現(KDTree)和球樹(BallTree)實現，所以他的這篇文章中只討論這幾種算法的實現原理。其餘的實現方法比如BBF樹，MVP樹等沒有做討論，需要對算法有更深一步了解的童鞋，移步劉建平Pinard的文章~
這一部分主要是參考實戰，然後主要講解一些具體的實現~
下面的代碼為運行程序導入所需要的庫
from numpy import *
import operator
下面的程序主要實現了生成測試數據的功能
def createDataSet():
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']
return group,labels
group,labels = createDataSet()
輸出：
In [2]:group
Out[2]: array([[ 1. , 1.1],
[ 1. , 1. ],
[ 0. , 0. ],
[ 0. , 0.1]])
In [3]: labels
Out[3]: ['A', 'A', 'B', 'B']
下面的代碼主要實現了利用knn分類的功能
def classify0(inX,dataSet,labels,k):
dataSetSize = dataSet.shape[0]
#tile 擴展矩陣的函數
diffMat = tile(inX,(dataSetSize,1))-dataSet
sqdiffMat = diffMat**2
sqDistances = sqdiffMat.sum(axis = 1)
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort()
print(sortedDistIndicies)
classCount={}
for i in range(k):
voteLabels = labels[sortedDistIndicies[i]]
#dict.get 獲取指定鍵的值，默認返回none，鍵值不存在時，不同於dict['key']直接返回error，也可以指定，下面指定為0
classCount[voteLabels] = classCount.get(voteLabels,0)+1
print(classCount)
#Python3.5中：iteritems變為items(python2 classCount.iteritems())
#items可以輸出dict中的（key，value）
#sorted中的key參數傳入函數，operator.itemgetterr函數獲取的不是值，而是定義了一個函數，通過該函數作用到對象上才能獲取值。
#operator.itemgetter(1) 為獲取classCount.items()中的第二個參數
sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
print(sortedClassCount)
return sortedClassCount[0][0]
In [7]: classify0([0,0.2],group,labels,2)
[3 2 1 0]
{'B': 2}
[('B', 2)]
Out[6]: 'B'
argsort()函數是將x中的元素從小到大排列，提取其對應的index(索引)，然後輸出到y。
輸出是按照從小到大的順序輸出的
例子：
import numpy as np
a = np.array([2,0,4,1,2,4,5])
a.argsort()
輸出為a從小到大排序後的index：
Out[12]: array([1, 3, 0, 4, 2, 5, 6], dtype=int64)
輸出為list的index，提取出來就是list從小到大的排序
a = {'name': 'wang'}
dict[『key』]輸出
a['age']
Out[16]: KeyError: 'age'
dict.get輸出：
a.get('age')
a.get('age', 10)
Out[17]: 10
dict[『key』]只能獲取存在的值，如果不存在則觸發KeyError
而dict.get(key, default=None)則如果不存在則返回一個默認值，如果設置了則是設置的，否則就是None
a = [1,2,1,4,3,5]
a.sort()
aOut[18]: [1, 1, 2, 3, 4, 5]
sort函數改變了a的順序
a = [1,2,1,4,3,5]
sorted(a)
aOut[19]: [1, 2, 1, 4, 3, 5]
sorted未改變a的順序
sorted函數list1 = [('david', 90), ('mary',90), ('sara',80),('lily',95)]
sorted(list1,cmp = lambda x,y: cmp(x[0],y[0]))
TypeError: 'cmp' is an invalid keyword argument for this function
sorted(list1,key = lambda list1: list1[0])
Out[23]: [('david', 90), ('lily', 95), ('mary', 90), ('sara', 80)]
list1[0]表示用list中的第一個元素排序
sorted(list1,key = lambda list1: list1[1])
Out[24]: [('sara', 80), ('david', 90), ('mary', 90), ('lily', 95)]
list1[1]表示用list中的第二個元素排序
三道sorted面試題1）key函數的運用
students = [('john', 'A', 15), ('jane', 'B', 12), ('dave','B', 10)]
sorted(students,key=lambda s: s[2]) #按照年齡來排序
2）多個字符的排序
『asdf234GDSdsf23』這是一個字符串排序，排序規則：小寫<大寫<奇數<偶數
s = 'asdf234GDSdsf23' #排序:小寫-大寫-奇數-偶數
#解法1：
print("".join(sorted(s, key=lambda x: (x.isdigit(),x.isdigit() and int(x) % 2 == 0,x.isupper(),x))))
Out[25]: addffssDGS33224
#解法2：
print("".join(sorted(s, key=lambda x: (x.isdigit(),x.isupper(),x.isdigit() and int(x) % 2 == 0,x))))
Out[26]: addffssDGS33224
解釋:
Boolean 的排序會將 False 排在前，True排在後 .
1.x.isdigit()的作用是把數字放在後邊,字母放在前邊.
2.x.isdigit() and int(x) % 2 == 0的作用是保證奇數在前，偶數在後。
3.x.isupper()的作用是在前面基礎上,保證字母小寫在前大寫在後.
4.最後的x表示在前面基礎上,對所有類別數字或字母排序。
若不進行第四步，每個內部是未排序的，但是整體順序是按照要求排序的
print("".join(sorted(s, key=lambda x: (x.isdigit(),x.isupper(),x.isdigit() and int(x) % 2 == 0))))
Out[27]: asdfdsfGDS33242
3） 特殊需求的排序
list1=[7, -8, 5, 4, 0, -2, -5]
要求1.正數在前負數在後 2.整數從小到大 3.負數從大到小
#解法1：
sorted(list1,key = lambda x:(x<0,x<0 and -x,x))
Out[28]: [0, 4, 5, 7, -2, -5, -8]
解法2：
sorted(list1,key=lambda x:(x<0,abs(x)))
Out[29]: [0, 4, 5, 7, -2, -5, -8]
講完這幾個函數，對照機器學習實戰的原始碼，理解和實現kNN算法就是手到擒來了~小編也是第一次嘗試這樣的寫作風格，有任何意見和想法請及時和小編聯繫，小編會繼續努力噠~
K近鄰法(KNN)原理小結
Python中sort 和 sorted函數
李航. 統計學習方法[M]. 清華大學出版社, 2012.
周志華. 機器學習 : = Machine learning[M]. 清華大學出版社, 2016.
哈林頓李銳. 機器學習實戰 : Machine learning in action[M]. 人民郵電出版社, 2013.
Python愛好者社區歷史文章大合集：
Python愛好者社區歷史文章列表（每周append更新一次）
福利：文末掃碼立刻關注公眾號，「Python愛好者社區」，開始學習Python課程：
關注後在公眾號內回復「課程」即可獲取：
0.小編的Python入門視頻課程！！！
1.崔老師爬蟲實戰案例免費學習視頻。
2.丘老師數據科學入門指導免費學習視頻。
3.陳老師數據分析報告製作免費學習視頻。
4.玩轉大數據分析！Spark2.X+Python 精華實戰課程免費學習視頻。
5.丘老師Python網絡爬蟲實戰免費學習視頻。