python機器學習案例教程—K最近鄰算法的實現

K最近鄰屬于一種分類算法，他的解釋最容易，近朱者赤，近墨者黑，我們想看一個人是什么樣的，看他的朋友是什么樣的就可以了。當然其他還牽著到，看哪方面和朋友比較接近（對象特征），怎樣才算是跟朋友親近，一起吃飯還是一起逛街算是親近（距離函數），根據朋友的優秀不優秀如何評判目標任務優秀不優秀（分類算法），是否不同優秀程度的朋友和不同的接近程度要考慮一下（距離權重），看幾個朋友合適（k值），能否以分數的形式表示優秀度（概率分布）。

K最近鄰概念：
它的工作原理是：存在一個樣本數據集合，也稱作為訓練樣本集，并且樣本集中每個數據都存在標簽，即我們知道樣本集中每一個數據與所屬分類的對應關系。輸入沒有標簽的新數據后，將新的數據的每個特征與樣本集中數據對應的特征進行比較，然后算法提取樣本最相似數據(最近鄰)的分類標簽。一般來說，我們只選擇樣本數據集中前k個最相似的數據，這就是k-近鄰算法中k的出處，通常k是不大于20的整數。最后，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。
今天我們使用k最近鄰算法來構建白酒的價格模型。
構造數據集
構建一個葡萄酒樣本數據集。白酒的價格跟等級、年代有很大的關系。
from random import random,randint
import math
 
# 根據等級和年代對價格進行模擬
def wineprice(rating,age):
 peak_age=rating-50
 
 # 根據等級計算價格
 price=rating/2
 if age>peak_age:
  # 經過“峰值年”，后續5年里其品質將會變差
  price=price*(5-(age-peak_age)/2)
 else:
  # 價格在接近“峰值年”時會增加到原值的5倍
  price=price*(5*((age+1)/peak_age))
 if price<0: price=0
 return price
 
# 生成一批模式數據代表樣本數據集
def wineset1():
 rows=[]
 for i in range(300):
  # 隨機生成年代和等級
  rating=random()*50+50
  age=random()*50
 
  # 得到一個參考價格
  price=wineprice(rating,age)
 
  # 添加一些噪音
  price*=(random()*0.2+0.9)
 
  # 加入數據集
  rows.append({'input':(rating,age),'result':price})
 return rows

數據間的距離

使用k最近鄰，首先要知道那些最近鄰，也就要求知道數據間的距離。我們使用歐幾里得距離作為數據間的距離。    
# 使用歐幾里得距離，定義距離
def euclidean(v1,v2):
 d=0.0
 for i in range(len(v1)):
  d+=(v1[i]-v2[i])**2
 return math.sqrt(d)

獲取與新數據距離最近的k個樣本數據    
# 計算給預測商品和原數據集中任一其他商品間的距離。data原數據集，vec1預測商品
def getdistances(data,vec1):
 distancelist=[]
 
 # 遍歷數據集中的每一項
 for i in range(len(data)):
  vec2=data[i]['input']
 
  # 添加距離到距離列表
  distancelist.append((euclidean(vec1,vec2),i))
 
 # 距離排序
 distancelist.sort()
 return distancelist #返回距離列表

根據距離最近的k個樣本數據預測新數據的屬性

1、簡單求均值
    
# 對距離值最小的前k個結果求平均
def knnestimate(data,vec1,k=5):
 # 得到經過排序的距離值
 dlist=getdistances(data,vec1)
 avg=0.0
 
 # 對前k項結果求平均
 for i in range(k):
  idx=dlist[i][1]
  avg+=data[idx]['result']
 avg=avg/k
 return avg

2、求加權平均

如果使用直接求均值，有可能存在前k個最近鄰中，可能會存在距離很遠的數據，但是他仍然屬于最近的前K個數據。當存在這種情況時，對前k個樣本數據直接求均值會有偏差，所以使用加權平均，為較遠的節點賦予較小的權值，對較近的節點賦予較大的權值。

那么具體該怎么根據數據間距離分配權值呢？這里使用三種遞減函數作為權值分配方法。

2.1、使用反函數為近鄰分配權重。    
def inverseweight(dist,num=1.0,const=0.1):
 return num/(dist+const)

2.2、使用減法函數為近鄰分配權重。當最近距離都大于const時不可用。
    
def subtractweight(dist,const=1.0):
 if dist>const:
  return 0
 else:
  return const-dist

2.3、使用高斯函數為距離分配權重。    
def gaussian(dist,sigma=5.0):
 return math.e**(-dist**2/(2*sigma**2))

有了權值分配方法，下面就可以計算加權平均了。
# 對距離值最小的前k個結果求加權平均
def weightedknn(data,vec1,k=5,weightf=gaussian):
 # 得到距離值
 dlist=getdistances(data,vec1)
 avg=0.0
 totalweight=0.0
 
 # 得到加權平均
 for i in range(k):
  dist=dlist[i][0]
  idx=dlist[i][1]
  weight=weightf(dist)
  avg+=weight*data[idx]['result']
  totalweight+=weight
 if totalweight==0: return 0
 avg=avg/totalweight
 return avg

第一次測試

上面完成了使用k最近鄰進行新數據預測的功能，下面我們進行測試。    
if __name__=='__main__': #只有在執行當前模塊時才會運行此函數
 data = wineset1()  #創建第一批數據集
 result=knnestimate(data,(95.0,3.0)) #根據最近鄰直接求平均進行預測
 print(result)
 
 result=weightedknn(data,(95.0,3.0),weightf=inverseweight) #使用反函數做權值分配方法，進行加權平均
 print(result)
 result = weightedknn(data, (95.0, 3.0), weightf=subtractweight) # 使用減法函數做權值分配方法，進行加權平均
 print(result)
 result = weightedknn(data, (95.0, 3.0), weightf=gaussian) # 使用高斯函數做權值分配方法，進行加權平均
 print(result)

交叉驗證

交叉驗證是用來驗證你的算法或算法參數的好壞，比如上面的加權分配算法我們有三種方式，究竟哪個更好呢？我們可以使用交叉驗證進行查看。

隨機選擇樣本數據集中95%作為訓練集，5%作為新數據，對新數據進行預測并與已知結果進行比較，查看算法效果。

要實現交叉驗證，要實現將樣本數據集劃分為訓練集和新數據兩個子集的功能。
    
# 劃分數據。test測試數據集占的比例。其他數據集為訓練數據
def dividedata(data,test=0.05):
 trainset=[]
 testset=[]
 for row in data:
  if random()    testset.append(row)
  else:
   trainset.append(row)
 return trainset,testset

還要能應用算法，計算預測結果與真實結果之間的誤差度。
    
# 使用數據集對使用算法進行預測的結果的誤差進行統計，一次判斷算法好壞。algf為算法函數，trainset為訓練數據集，testset為預測數據集
def testalgorithm(algf,trainset,testset):
 error=0.0
 for row in testset:
  guess=algf(trainset,row['input']) #這一步要和樣本數據的格式保持一致，列表內個元素為一個字典，每個字典包含input和result兩個屬性。而且函數參數是列表和元組
  error+=(row['result']-guess)**2
  #print row['result'],guess
 #print error/len(testset)
 return error/len(testset)

有了數據拆分和算法性能誤差統計函數。我們就可以在原始數據集上進行多次這樣的實驗，統計平均誤差。
    
# 將數據拆分和誤差統計合并在一起。對數據集進行多次劃分，并驗證算法好壞
def crossvalidate(algf,data,trials=100,test=0.1):
 error=0.0
 for i in range(trials):
  trainset,testset=dividedata(data,test)
  error+=testalgorithm(algf,trainset,testset)
 return error/trials

交叉驗證測試    
if __name__=='__main__': #只有在執行當前模塊時才會運行此函數
 data = wineset1()  #創建第一批數據集
 print(data)
  error = crossvalidate(knnestimate,data) #對直接求均值算法進行評估
 print('平均誤差：'+str(error))
 
 def knn3(d,v): return knnestimate(d,v,k=3) #定義一個函數指針。參數為d列表，v元組
 error = crossvalidate(knn3, data)   #對直接求均值算法進行評估
 print('平均誤差：' + str(error))
 
 def knninverse(d,v): return weightedknn(d,v,weightf=inverseweight) #定義一個函數指針。參數為d列表，v元組
 error = crossvalidate(knninverse, data)   #對使用反函數做權值分配方法進行評估
 print('平均誤差：' + str(error))

不同類型、值域的變量、無用變量

在樣本數據的各個屬性中可能并不是取值范圍相同的同類型的數據，比如上面的酒的屬性可能包含檔次（0-100），酒的年限（0-50），酒的容量（三種容量375.0ml、750.0ml、1500.0ml），甚至在我們獲取的樣本數據中還有可能包含無用的數據，比如酒生產的流水線號（1-20之間的整數）。在計算樣本距離時，取值范圍大的屬性的變化會嚴重影響取值范圍小的屬性的變化，以至于結果會忽略取值范圍小的屬性。而且無用屬性的變化也會增加數據之間的距離。

所以就要對樣本數據的屬性進行縮放到合適的范圍，并要能刪除無效屬性。

構造新的數據集
    
# 構建新數據集，模擬不同類型變量的問題
def wineset2():
 rows=[]
 for i in range(300):
  rating=random()*50+50 #酒的檔次
  age=random()*50   #酒的年限
  aisle=float(randint(1,20)) #酒的通道號（無關屬性）
  bottlesize=[375.0,750.0,1500.0][randint(0,2)] #酒的容量
  price=wineprice(rating,age) #酒的價格
  price*=(bottlesize/750)
  price*=(random()*0.2+0.9)
  rows.append({'input':(rating,age,aisle,bottlesize),'result':price})
 return rows

實現按比例對屬性的取值進行縮放的功能
    
# 按比例對屬性進行縮放，scale為各屬性的值的縮放比例。
def rescale(data,scale):
 scaleddata=[]
 for row in data:
  scaled=[scale[i]*row['input'][i] for i in range(len(scale))]
  scaleddata.append({'input':scaled,'result':row['result']})
 return scaleddata

那就剩下最后最后一個問題，究竟各個屬性縮放多少呢。這是一個優化問題，我們可以通過優化技術尋找最優化解。而需要優化的成本函數，就是通過縮放以后進行預測的結果與真實結果之間的誤差值。誤差值越小越好。誤差值的計算同前面交叉驗證時使用的相同crossvalidate函數

下面構建成本函數    
# 生成成本函數。閉包
def createcostfunction(algf,data):
 def costf(scale):
  sdata=rescale(data,scale)
  return crossvalidate(algf,sdata,trials=10)
 return costf
 
weightdomain=[(0,10)]*4  #將縮放比例這個題解的取值范圍設置為0-10，可以自己設定，用于優化算法

優化技術的可以參看http://www.jb51.net/article/131719.htm

測試代碼    
if __name__=='__main__': #只有在執行當前模塊時才會運行此函數
 #========縮放比例優化===
 data = wineset2() # 創建第2批數據集
 print(data)
 import optimization
 costf=createcostfunction(knnestimate,data)  #創建成本函數
 result = optimization.annealingoptimize(weightdomain,costf,step=2) #使用退火算法尋找最優解
 print(result)

不對稱分布

對于樣本數據集包含多種分布情況時，輸出結果我們也希望不唯一。我們可以使用概率結果進行表示，輸出每種結果的值和出現的概率。

比如葡萄酒有可能是從折扣店購買的，而樣本數據集中沒有記錄這一特性。所以樣本數據中價格存在兩種形式的分布。

構造數據集    
def wineset3():
 rows=wineset1()
 for row in rows:
  if random()<0.5:
   # 葡萄酒是從折扣店購買的
   row['result']*=0.6
 return rows

如果以結果概率的形式存在，我們要能夠計算指定范圍的概率值
    
# 計算概率。data樣本數據集，vec1預測數據，low，high結果范圍，weightf為根據距離進行權值分配的函數
def probguess(data,vec1,low,high,k=5,weightf=gaussian):
 dlist=getdistances(data,vec1) #獲取距離列表
 nweight=0.0
 tweight=0.0
 
 for i in range(k):
  dist=dlist[i][0] #距離
  idx=dlist[i][1] #索引號
  weight=weightf(dist) #權值
  v=data[idx]['result'] #真實結果
 
  # 當前數據點位于指定范圍內么？
  if v>=low and v<=high:
   nweight+=weight #指定范圍的權值之和
  tweight+=weight  #總的權值之和
 if tweight==0: return 0
 
 # 概率等于位于指定范圍內的權重值除以所有權重值
 return nweight/tweight

對于多種輸出、以概率和值的形式表示的結果，我們可以使用累積概率分布圖或概率密度圖的形式表現。

繪制累積概率分布圖
    
from pylab import *
 
# 繪制累積概率分布圖。data樣本數據集，vec1預測數據，high取值最高點，k近鄰范圍，weightf權值分配
def cumulativegraph(data,vec1,high,k=5,weightf=gaussian):
 t1=arange(0.0,high,0.1)
 cprob=array([probguess(data,vec1,0,v,k,weightf) for v in t1]) #預測產生的不同結果的概率
 plot(t1,cprob)
 show()

繪制概率密度圖
    
# 繪制概率密度圖
def probabilitygraph(data,vec1,high,k=5,weightf=gaussian,ss=5.0):
 # 建立一個代表價格的值域范圍
 t1=arange(0.0,high,0.1)
 
 # 得到整個值域范圍內的所有概率
 probs=[probguess(data,vec1,v,v+0.1,k,weightf) for v in t1]
 
 # 通過加上近鄰概率的高斯計算結果，對概率值做平滑處理
 smoothed=[]
 for i in range(len(probs)):
  sv=0.0
  for j in range(0,len(probs)):
   dist=abs(i-j)*0.1
   weight=gaussian(dist,sigma=ss)
   sv+=weight*probs[j]
  smoothed.append(sv)
 smoothed=array(smoothed)
 
 plot(t1,smoothed)
 show()

測試代碼    
if __name__=='__main__': #只有在執行當前模塊時才會運行此函數
 
 data = wineset3() # 創建第3批數據集
 print(data)
 cumulativegraph(data,(1,1),120) #繪制累積概率密度
 probabilitygraph(data,(1,1),6) #繪制概率密度圖

以上就是本文的全部內容，希望對大家的學習有所幫助。