|
1、最鄰近算法
KNN方法的簡(jiǎn)單描述：
KNN方法用于分類(lèi)，其基本思想如下。我們已經(jīng)有一些已知類(lèi)型的數(shù)據(jù)，暫稱(chēng)其為訓(xùn)練集。當(dāng)一個(gè)新數(shù)據(jù)（暫稱(chēng)其為測(cè)試集）進(jìn)入的時(shí)候，開(kāi)始跟訓(xùn)練集數(shù)據(jù)中的每個(gè)數(shù)據(jù)點(diǎn)求距離，挑選與這個(gè)訓(xùn)練數(shù)據(jù)集中最近的K個(gè)點(diǎn)看這些點(diǎn)屬于什么類(lèi)型，用少數(shù)服從多數(shù)的方法將測(cè)試數(shù)據(jù)歸類(lèi)。
圖示： 這里我用一個(gè)常見(jiàn)到的圖做介紹：1、有三類(lèi)已知數(shù)據(jù)集（訓(xùn)練集），它們分別屬于w1、w2、w3，這三類(lèi)數(shù)據(jù)分別有自己的特征；2、有一個(gè)位置類(lèi)別的數(shù)據(jù)（測(cè)試集）Xu；3、通過(guò)求Xu點(diǎn)到所有訓(xùn)練集數(shù)據(jù)的距離，取距離最近的n個(gè)點(diǎn)，查看這n個(gè)點(diǎn)所歸屬的類(lèi)別，以少數(shù)服從多數(shù)的方式將Xu歸類(lèi)到已知訓(xùn)練集下
2、python實(shí)現(xiàn)最鄰近算法案例
這里我構(gòu)造了一個(gè)150*5的矩陣，分別代表三類(lèi)數(shù)據(jù)。每行的前四個(gè)值代表數(shù)據(jù)的特征，第五個(gè)值代表數(shù)據(jù)的類(lèi)別。如圖：
這三類(lèi)數(shù)據(jù)分別屬于apple、banana、orange
第一步：加載數(shù)據(jù)。 以split參數(shù)傳來(lái)的參數(shù)為限，將小于split的隨機(jī)數(shù)對(duì)應(yīng)的數(shù)據(jù)劃分到訓(xùn)練集，將大于split的隨機(jī)數(shù)劃分到測(cè)試集
def loadDataset(self,filename, split, trainingSet, testSet): # 加載數(shù)據(jù)集 split以某個(gè)值為界限分類(lèi)train和test
with open(filename, 'r') as csvfile:
lines = csv.reader(csvfile) #讀取所有的行
dataset = list(lines) #轉(zhuǎn)化成列表
for x in range(len(dataset)-1):
for y in range(4):
dataset[x][y] = float(dataset[x][y])
if random.random() < split: # 將所有數(shù)據(jù)加載到train和test中
trainingSet.append(dataset[x])
else:
testSet.append(dataset[x])
第二步：對(duì)每個(gè)測(cè)試集中的數(shù)據(jù)進(jìn)行迭代，取其臨近點(diǎn)。
計(jì)算測(cè)試集中每個(gè)點(diǎn)到訓(xùn)練集中每個(gè)點(diǎn)的距離，將這些距離按從小到大進(jìn)行排序，取最近的k個(gè)點(diǎn)作為歸類(lèi)點(diǎn)
def getNeighbors(self,trainingSet, testInstance, k): # 返回最近的k個(gè)邊距
distances = []
length = len(testInstance)-1
for x in range(len(trainingSet)): #對(duì)訓(xùn)練集的每一個(gè)數(shù)計(jì)算其到測(cè)試集的實(shí)際距離
dist = self.calculateDistance(testInstance, trainingSet[x], length)
print('{}--{}'.format(trainingSet[x], dist))
distances.append((trainingSet[x], dist))
distances.sort(key=operator.itemgetter(1)) # 把距離從小到大排列
neighbors = []
for x in range(k): #排序完成后取前k個(gè)距離
neighbors.append(distances[x][0])
return neighbors
計(jì)算距離函數(shù)
def calculateDistance(self,testdata, traindata, length): # 計(jì)算距離
distance = 0 # length表示維度 數(shù)據(jù)共有幾維
for x in range(length):
distance += pow((testdata[x]-traindata[x]), 2)
return math.sqrt(distance)
length表示維度，這里數(shù)據(jù)是4維
第三步：判斷那k個(gè)點(diǎn)所屬的類(lèi)別，選擇出現(xiàn)頻率最大的類(lèi)標(biāo)號(hào)作為測(cè)試集的類(lèi)標(biāo)號(hào)
def getResponse(self,neighbors): # 根據(jù)少數(shù)服從多數(shù)，決定歸類(lèi)到哪一類(lèi)
classVotes = {}
for x in range(len(neighbors)):
response = neighbors[x][-1] # 統(tǒng)計(jì)每一個(gè)分類(lèi)的多少
if response in classVotes:
classVotes[response] += 1
else:
classVotes[response] = 1
print(classVotes.items())
sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True) #reverse按降序的方式排列
return sortedVotes[0][0]
計(jì)算距離：
結(jié)果：
代碼和測(cè)試數(shù)據(jù)點(diǎn)這里 ：密碼：iaqr
如果嫌下載麻煩，這里是全部code：
# -*- coding: UTF-8 -*-
import math
import csv
import random
import operator
'''
@author:hunter
@time:2017.03.31
'''
class KNearestNeighbor(object):
def __init__(self):
pass
def loadDataset(self,filename, split, trainingSet, testSet): # 加載數(shù)據(jù)集 split以某個(gè)值為界限分類(lèi)train和test
with open(filename, 'r') as csvfile:
lines = csv.reader(csvfile) #讀取所有的行
dataset = list(lines) #轉(zhuǎn)化成列表
for x in range(len(dataset)-1):
for y in range(4):
dataset[x][y] = float(dataset[x][y])
if random.random() < split: # 將所有數(shù)據(jù)加載到train和test中
trainingSet.append(dataset[x])
else:
testSet.append(dataset[x])
def calculateDistance(self,testdata, traindata, length): # 計(jì)算距離
distance = 0 # length表示維度 數(shù)據(jù)共有幾維
for x in range(length):
distance += pow((testdata[x]-traindata[x]), 2)
return math.sqrt(distance)
def getNeighbors(self,trainingSet, testInstance, k): # 返回最近的k個(gè)邊距
distances = []
length = len(testInstance)-1
for x in range(len(trainingSet)): #對(duì)訓(xùn)練集的每一個(gè)數(shù)計(jì)算其到測(cè)試集的實(shí)際距離
dist = self.calculateDistance(testInstance, trainingSet[x], length)
print('訓(xùn)練集:{}-距離:{}'.format(trainingSet[x], dist))
distances.append((trainingSet[x], dist))
distances.sort(key=operator.itemgetter(1)) # 把距離從小到大排列
neighbors = []
for x in range(k): #排序完成后取前k個(gè)距離
neighbors.append(distances[x][0])
print(neighbors)
return neighbors
def getResponse(self,neighbors): # 根據(jù)少數(shù)服從多數(shù)，決定歸類(lèi)到哪一類(lèi)
classVotes = {}
for x in range(len(neighbors)):
response = neighbors[x][-1] # 統(tǒng)計(jì)每一個(gè)分類(lèi)的多少
if response in classVotes:
classVotes[response] += 1
else:
classVotes[response] = 1
print(classVotes.items())
sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True) #reverse按降序的方式排列
return sortedVotes[0][0]
def getAccuracy(self,testSet, predictions): # 準(zhǔn)確率計(jì)算
correct = 0
for x in range(len(testSet)):
if testSet[x][-1] == predictions[x]: #predictions是預(yù)測(cè)的和testset實(shí)際的比對(duì)
correct += 1
print('共有{}個(gè)預(yù)測(cè)正確，共有{}個(gè)測(cè)試數(shù)據(jù)'.format(correct,len(testSet)))
return (correct/float(len(testSet)))*100.0
def Run(self):
trainingSet = []
testSet = []
split = 0.75
self.loadDataset(r'testdata.txt', split, trainingSet, testSet) #數(shù)據(jù)劃分
print('Train set: ' + str(len(trainingSet)))
print('Test set: ' + str(len(testSet)))
#generate predictions
predictions = []
k = 3 # 取最近的3個(gè)數(shù)據(jù)
# correct = []
for x in range(len(testSet)): # 對(duì)所有的測(cè)試集進(jìn)行測(cè)試
neighbors = self.getNeighbors(trainingSet, testSet[x], k) #找到3個(gè)最近的鄰居
result = self.getResponse(neighbors) # 找這3個(gè)鄰居歸類(lèi)到哪一類(lèi)
predictions.append(result)
# print(correct)
accuracy = self.getAccuracy(testSet,predictions)
print('Accuracy: ' + repr(accuracy) + '%')
if __name__ == '__main__':
a = KNearestNeighbor()
a.Run()
正在學(xué)習(xí)Python中的朋友們需要學(xué)習(xí)資料交流平臺(tái)可以加群 點(diǎn)擊鏈接加入群【python】：https://jq.qq.com/?_wv=1027&k=42CGd8i 部落官方學(xué)習(xí)群號(hào) 463024091（←長(zhǎng)按可復(fù)制） 每天晚上都有大神與你高清視頻免費(fèi)分享交流行業(yè)最新動(dòng)態(tài)
|
