Python 2.7
IDE Pycharm 5.0.3
numpy 1.11.0

前言

總算邁入機器學(xué)習第一步，總比原地踏步要好。

什么是K-近鄰?

一句話總結(jié)，物以類聚，人以群分，更‘靠近’哪一個點，就認為它屬于那一個點。以一篇碩士論文截圖說明

這里寫圖片描述

Knn算法思想

Knn偽代碼

根據(jù)這個偽代碼流程，我們就可以使用python進行算法重構(gòu)了，分三步，一算距離，二排序，三取值

實現(xiàn)Knn基礎(chǔ)代碼

第一部分，被調(diào)函數(shù)，在主程序中需要導(dǎo)入

# -*- coding: utf-8 -*-
from numpy import *
import operator


def creatDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels


def classify0(inX,dataSet,labels,k): # inX用于需要分類的數(shù)據(jù)，dataSet輸入訓(xùn)練集


    ######輸入與訓(xùn)練樣本之間的距離計算######
    dataSetSize = dataSet.shape[0] # 讀取行數(shù),shape[1]則為列數(shù)
    diffMat = tile(inX,(dataSetSize,1))-dataSet # tile,重復(fù)inX數(shù)組的行(dataSize)次，列重復(fù)1
    sqDiffMat = diffMat**2 #平方操作
    sqDistances = sqDiffMat.sum(axis=1) # 每一個列向量相加,axis=0為行相加
    distances = sqDistances**0.5

    sortedDistIndicies = distances.argsort() # argsort函數(shù)返回的是數(shù)組值從小到大的索引值
    #print sortedDistIndicies #產(chǎn)生的是一個排序號組成的矩陣
    classCount={}

    ######累計次數(shù)構(gòu)成字典######
    for i in range(k):
        #print sortedDistIndicies[i]
        voteIlabel = labels[sortedDistIndicies[i]] #排名前k個貼標簽
        #print voteIlabel
        classCount[voteIlabel] = classCount.get(voteIlabel,0)+1 # 不斷累加計數(shù)的過程，體現(xiàn)在字典的更新中
        #print classCount.get(voteIlabel,0)
        #print classCount
        #get(key,default=None),就是造字典


    ######找到出現(xiàn)次數(shù)最大的點######
    sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse=True)
    #以value值大小進行排序，reverse=True降序
    #print classCount.iteritems()
    #print sortedClassCount
    #key = operator.itemgetter(1)，operator.itemgetter函數(shù)獲取的不是值，而是定義了一個函數(shù)，通過該函數(shù)作用到對象上才能獲取值

    return sortedClassCount[0][0]
    #返回出現(xiàn)次數(shù)最多的value的key

第二部分，主程序部分，只要將主程序和被調(diào)函數(shù)放在同一工作目錄下，直接運行主程序即可

# -*- coding: utf-8 -*-
import Knn_bymyself

group,labels = Knn_bymyself.creatDataSet() # 調(diào)用Knn_bymyself中的creatDataSet()方法
while 1:
    try:
        a=input('please input x:')
        b=input('please input y:')
        #classify0(inX,dataSet,labels,k)對應(yīng)起來看
        print 'belong to :'+Knn_bymyself.classify0([a,b],group,labels,3)+' class'
    except:
        break

跑出來大概是這樣的：

please input x:2
please input y:1
belong to :A class

分析一下

group也就是輸入訓(xùn)練集，label就是訓(xùn)練集代表的標簽

從圖形上分析

表現(xiàn)形式

從上圖可以看出，我測試的點是(2,1)，明顯可以看出它是距離A類比較靠近，所以歸屬于A類沒有問題。

再從算法上分析；
計算unknown點到每個點的距離，然后取最小距離的K個點，在K個點中，哪個類出現(xiàn)的概率高就歸屬于哪一類，應(yīng)該沒什么問題了。

你可能需要的知道

先過一眼NumPy快速入門→點擊這里快速學(xué)習NumPy

附加：上述代碼中出現(xiàn)的方法使用解析

In[138]: marray
Out[138]: 
array([[1, 2, 3],
       [4, 5, 6]])

• sum(axis= )，行(列)相加形成新的行(列)

In[135]: marray.sum(axis=0)
Out[135]: array([5, 7, 9])

• tile(a,(n,m))，將數(shù)組a的行重復(fù)n次，列重復(fù)m次

In[136]: b = tile(marray,(2,3))
In[137]: b
Out[137]: 
array([[1, 2, 3, 1, 2, 3, 1, 2, 3],
       [4, 5, 6, 4, 5, 6, 4, 5, 6],
       [1, 2, 3, 1, 2, 3, 1, 2, 3],
       [4, 5, 6, 4, 5, 6, 4, 5, 6]])

dict.get(k,d)
get相當于一條if...else...語句,參數(shù)k在字典中，字典將返回dict[k]也就是k對應(yīng)的value值；如果參數(shù)k不在字典中則返回參數(shù)d。

舉栗子

In[149]: dict = {'A':1,'B':2}
In[150]: dict.get('A',0)
Out[150]: 1
In[151]: dict.get('C',1)
Out[151]: 1

• .iteritems()迭代器的使用

#使用next()
In[165]: dict.iteritems().next()
Out[164]: ('A', 1)

#使用for循環(huán)
In[169]: for i in dict.iteritems():
...     print i
...     
('A', 1)
('B', 2)

#轉(zhuǎn)化成list之后檢索
In[170]: list_dict = list(dict.iteritems())
In[171]: list_dict[0]

Out[170]: ('A', 1)

最后

 這里只是解釋了如何使用最基本的KNN的方法，代碼也是最簡單的，配合圖的講解，應(yīng)該會更加清楚一些，代碼我抄自機器學(xué)習，但是它的解釋比較少，算是加上了自己的備注，也算是自己的一個學(xué)習過程吧，希望對你也有幫助

附錄

如果你對那副點陣圖感興趣，也是用python寫的代碼如下，可作參考。

# -*- coding: utf-8 -*-

import matplotlib.pyplot as plt
plt.title("KNN ")
plt.xlim(xmax=2.2,xmin=0)
plt.ylim(ymax=2.2,ymin=0)

#標識箭頭
plt.annotate("unknown", xy = (2, 1), xytext = (1.5, 2), arrowprops = dict(facecolor = 'black', shrink = 0.1))
plt.annotate("A class", xy = (1, 1.2), xytext = (1, 2), arrowprops = dict(facecolor = 'black', shrink = 0.1))
plt.annotate("B class", xy = (0.1,0.1), xytext = (0.5,1), arrowprops = dict(facecolor = 'black', shrink = 0.1))

plt.xlabel("x")
plt.ylabel("y")
plt.plot([1,1,0,0],[1.1,1,0,0.1],'ro') # A.B類的點陣
plt.plot([2],[1],'ro') # unknown點
plt.show()

致謝

利用python進行數(shù)據(jù)分析.Wes McKinney著
機器學(xué)習實戰(zhàn).Peter Harrington著
@jihite--字典訪問的三種方法
@MrLevo520--numpy快速入門