python機(jī)器學(xué)習(xí)實(shí)踐：KNN算法

  • k-Nearest Neighbors算法（簡稱KNN算法，k近鄰算法），是一個(gè)邏輯很簡單的分類算法，其核心原理是找到與被測數(shù)據(jù)距離最近的k個(gè)數(shù)據(jù)，這k個(gè)數(shù)據(jù)中最多的類別就是預(yù)測數(shù)據(jù)的類別，而這個(gè)距離用的是歐式距離。
  • knn算法幾乎沒有訓(xùn)練過程，實(shí)現(xiàn)簡單，但是計(jì)算復(fù)雜性高；空間復(fù)雜性高；一般數(shù)值很大的時(shí)候不用這個(gè)，計(jì)算量太大。但是單個(gè)樣本又不能太少，否則容易發(fā)生誤分，最大的缺點(diǎn)是無法給出數(shù)據(jù)的內(nèi)在含義

knn算法python實(shí)現(xiàn)

1. 直接使用python sklearn庫

十來行代碼就能搞定，高效快捷

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
#加載數(shù)據(jù)
iris = datasets.load_iris()
iris_x = iris.data
iris_y = iris.target
#分割數(shù)據(jù)，30%用做測試集
x_train, x_test, y_train, y_test = train_test_split(iris_x, iris_y, test_size=0.3)
#訓(xùn)練模型，預(yù)測數(shù)據(jù)
knn = KNeighborsClassifier()
knn.fit(x_train, y_train)
print(knn.predict(x_test))
print(y_test)

其中iris數(shù)據(jù)是分類鳶尾花數(shù)據(jù)，sklearn內(nèi)置的，當(dāng)然也可以下載原數(shù)據(jù)，鏈接：https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data

2. 不使用庫，徒手寫knn實(shí)現(xiàn)

KNN算法分為如下幾步：

  • 數(shù)據(jù)處理：打開CSV文件獲取數(shù)據(jù)，將原始數(shù)據(jù)分為測試集/訓(xùn)練集。

  • 相似性度量：計(jì)算每兩個(gè)數(shù)據(jù)實(shí)例之間的距離。

  • 近鄰查找：找到k個(gè)與當(dāng)前數(shù)據(jù)最近的鄰居。

  • 結(jié)果反饋：從近鄰實(shí)例反饋結(jié)果。

  • 精度評估：統(tǒng)計(jì)預(yù)測精度。

  • 主函數(shù)：將上述過程串起來。

2.1 數(shù)據(jù)處理

首先加載文件中的數(shù)據(jù)。示例中使用的是csv module中的reader函數(shù)去讀取文件。其實(shí)可以直接按行讀取處理成想要的數(shù)據(jù)類型，不需要引入csv模塊，因人而異。

接下來，將數(shù)據(jù)拆分為kNN用于做預(yù)測的訓(xùn)練集(training dataset)和用來評估模型精度的測試集(test dataset)。。通常訓(xùn)練集/測試集的劃分比例標(biāo)準(zhǔn)為67/33。

將上述步驟合在一起，我們可以定義一個(gè)叫l(wèi)oadDataset的函數(shù)，該函數(shù)可以加載指定的CSV文件，并按照指定的比例隨機(jī)分為訓(xùn)練集與測試集。

def loadDataset(filename, split, trainingSet=[] , testSet=[]):
    with open(filename, 'rb') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        for x in range(len(dataset)-1):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
            if random.random() < split:
                trainingSet.append(dataset[x])
            else:
                 testSet.append(dataset[x])
#測試函數(shù)
trainingSet=[]
testSet=[]
loadDataset('iris.data', 0.66, trainingSet, testSet)
print 'Train: ' , len(trainingSet)
print 'Test: ', len(testSet)

2.2 相似度度量（計(jì)算距離）

為了進(jìn)行預(yù)測我們需要計(jì)算任意兩個(gè)數(shù)據(jù)實(shí)例的相似性。對于給定的每一個(gè)測試集中的數(shù)據(jù)實(shí)例，我們都可以在訓(xùn)練集中找出k個(gè)相似性最高的數(shù)據(jù)實(shí)例，這樣就可以依次進(jìn)行預(yù)測。

假定鳶尾花的4個(gè)測量數(shù)據(jù)都為數(shù)值形式且單位相同，我們可以直接采用歐氏距離(Euclidean distance)進(jìn)行相似性度量。歐式距離定義為：兩組向量對應(yīng)元素之差的平方和再做平方根運(yùn)算。

將上述步驟合在一起，我們可以將euclideanDistance函數(shù)定義為：

import math
def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)
#測試函數(shù)
data1 = [2, 2, 2, 'a']
data2 = [4, 4, 4, 'b']
distance = euclideanDistance(data1, data2, 3)
print 'Distance: ' , distance

2.3 近鄰查找

采用相似性度量的方法尋找未知數(shù)據(jù)實(shí)例的k個(gè)相似性最高的實(shí)例。

處理過程直接計(jì)算所有樣本點(diǎn)到給定點(diǎn)的歐式距離，進(jìn)而篩選距離最近的樣本點(diǎn)子集。

下面是getNeighbors函數(shù)，該函數(shù)遍歷訓(xùn)練集并返回與測試實(shí)例距離最近的k個(gè)近鄰樣本點(diǎn)（采用已經(jīng)定義好的euclideanDistance函數(shù)）。

def getNeighbors(trainingSet, testInstance, k):
    distances = []
    length = len(testInstance)-1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors
#測試函數(shù)
trainSet = [[2, 2, 2, 'a'], [4, 4, 4, 'b']]
testInstance = [5, 5, 5]
k = 1
neighbors = getNeighbors(trainSet, testInstance, 1)
print(neighbors)

2.4 結(jié)果預(yù)測

我們已經(jīng)找到了測試實(shí)例的最近的鄰居，下一步就是基于這些近鄰做出預(yù)測結(jié)果。
我們可以讓每個(gè)鄰居對測試實(shí)例的類別屬性進(jìn)行投票，最終以票數(shù)多者做為預(yù)測結(jié)果。
下面的函數(shù)提供了從近鄰?fù)镀敝蟹答伓鄶?shù)投票結(jié)果的機(jī)制。該函數(shù)假定每個(gè)鄰居的最后一列為類別屬性。

import operator
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]
#測試函數(shù)
neighbors = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
response = getResponse(neighbors)
print(response)

該方法在平局的情況下依然會(huì)有一個(gè)返回結(jié)果，但是我們可以對其特殊處理，例如返回空值或者選擇一個(gè)無偏隨機(jī)結(jié)果

2.5 精度評估

評估模型精度最簡單的方法就是計(jì)算正確預(yù)測結(jié)果數(shù)量占全部預(yù)測結(jié)果數(shù)量的比例，稱為分類精度。下面是getAccuracy函數(shù)，該函數(shù)統(tǒng)計(jì)所有的正確預(yù)測并返回正確分類的百分比精度。

def getAccuracy(testSet, predictions):
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] == predictions[x]:
            correct += 1
    return (correct/float(len(testSet))) * 100.0
#測試函數(shù)
testSet = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
predictions = ['a', 'a', 'a']
accuracy = getAccuracy(testSet, predictions)
print(accuracy)

2.6 主函數(shù)（串聯(lián)步驟2.1～2.5）

目前為止，我們已經(jīng)具備了所有的算法組成元素，下面我們將這些元素串起來，組成主函數(shù)。
下面是從零開始實(shí)現(xiàn)的kNN算法完整Python代碼。

# Example of kNN implemented from Scratch in Python

import csv
import random
import math
import operator

def loadDataset(filename, split, trainingSet=[] , testSet=[]):
    with open(filename, 'rb') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        for x in range(len(dataset)-1):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
            if random.random() < split:
                trainingSet.append(dataset[x])
            else:
                 testSet.append(dataset[x])
def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)
def getNeighbors(trainingSet, testInstance, k):
    distances = []
    length = len(testInstance)-1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]
def getAccuracy(testSet, predictions):
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] == predictions[x]:
            correct += 1
    return (correct/float(len(testSet))) * 100.0
def main():
    # prepare data
    trainingSet=[]
    testSet=[]
    split = 0.67
    loadDataset('iris.data', split, trainingSet, testSet)
    print 'Train set: ' + repr(len(trainingSet))
    print 'Test set: ' + repr(len(testSet))
    # generate predictions
    predictions=[]
    k = 3
    for x in range(len(testSet)):
        neighbors = getNeighbors(trainingSet, testSet[x], k)
        result = getResponse(neighbors)
        predictions.append(result)
        print('predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
    accuracy = getAccuracy(testSet, predictions)
    print('Accuracy: ' + repr(accuracy) + '%')

if __name__ == '__main__':
    main()

參考

http://python.jobbole.com/87407/
https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data
https://blog.csdn.net/Gamer_gyt/article/details/51232210

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容