knn演算法python代碼

Ⅰ 簡單數字識別(knn演算法)

knn演算法，即k-NearestNeighbor，後面的nn意思是最近鄰的意思，前面的k是前k個的意思，就是找到前k個離得最近的元素

離得最近這個詞具體實現有很多種，我使用的是歐式幾何中的距離公式

二維中兩點x(x1,y1),y(x2,y2)間距離公式為sqrt( (x1-x2)^2+(y1-y2)^2 )

推廣到n維就是

x(x1,x2, … ,xn),y(y1,y2, … ,yn)

sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)

knn演算法是要計算距離的，也就是數字之間的運算，而圖像是png，jpg這種格式，並不是數字也不能直接參與運算，所以我們需要進行一下轉換

如圖所示一個數字8，首先要確定的是這一步我做的是一個最簡單的轉換，因為我假定背景和圖之間是沒有雜物的，而且整個圖只有一個數字（0-9）如果遇到其他情況，比如背景色不純或者有其他干擾圖像需要重新設計轉換函數

接下來就是最簡單的轉換，將圖片白色部分（背景）變0，有圖像的部分變1。轉換後的大小要合適，太小會影響識別准確度，太大會增加計算量。所攜悄塌以我用的是書上的32*32，轉換後結果如圖所示

這樣一來，圖片就變成了能進行計算的數字了。

接下來我們需要創建一個庫，這個庫裡面存著0-9這些數字的各種類似上圖的實例。因為我們待識別的圖像要進行對比，選出辯圓前k個最近的，比較的對象就是我們的庫。假定庫中有0-9十個數字，每個數字各有100個這種由0和1表示的實例，那麼我們就有了一共1000個實例。

最後一步就是進行對比，利用開頭說的歐式幾何距離計算公式，首先這個32*32的方陣要轉換成一個1*1024的1024維坐標表示，然後拿這個待識別的圖像和庫中的1000個實例進行距離計算，選出前k個距離最近的。比如50個，這50個裡面出現次數最多的數字除以50就是結果數字的概率。比如50個裡面數字8出現40次，那麼待識別數字是8的可能性就是40/50 = 80%

個人理解：

只能識別單個數字，背景不能有干擾。如果想多數字識別或者背景有干擾需要針對具體情況考慮具體的圖像轉01的方法。

數字運冊識別非常依賴庫中的圖像，庫中的圖像的樣子嚴重影響圖像的識別（因為我們是和庫中的一一對比找出距離最近的前k個），所以數字的粗細，高低，胖瘦等待都是決定性因素，建庫時一定全面考慮數字的可能樣子

計算量比較大，待識別圖像要和庫中所有實例一一計算，如果使用32*32，就已經是1024維了。如果庫中有1000個，那就是1024維向量之間的1000次計算，圖像更清晰，庫更豐富只會使計算量更大

對於其他可以直接計算距離的數值型問題，可以用歐式距離，也可以用其他能代表距離的計算公式，對於非數值型的問題需要進行合適的轉換，轉換方式很重要，我覺得首先信息不能丟失，其次要精確不能模糊，要實現圖片轉換前後是一對一的關系

參考資料：機器學習實戰 [美] Peter Harrington 人民郵電出版社

python源碼

import numpy

import os

from PIL import Image

import heapq

from collections import Counter

def pictureconvert(filename1,filename2,size=(32,32)):

    #filename1待識別圖像，filename2 待識別圖像轉換為01txt文件輸出，size圖像大小，默認32*32

    image_file = Image.open(filename1)

    image_file = image_file.resize(size)

    width,height = image_file.size

    f1 = open(filename1,'r')

    f2 = open(filename2,'w')

    for i in range(height):

        for j in range(width):

            pixel = image_file.getpixel((j,i))

            pixel = pixel[0] + pixel[1] + pixel[2]

            if(pixel == 0):

                pixel = 0

            elif(pixel != 765 and pixel != 0):

                pixel = 1

            # 0代表黑色（無圖像），255代表白色（有圖像）

            # 0/255 = 0,255/255 = 1

            f2.write(str(pixel))

            if(j == width-1):

                f2.write('\n')

    f1.close()

    f2.close()

def imgvector(filename):

    #filename將待識別圖像的01txt文件轉換為向量

    vector = numpy.zeros((1,1024),numpy.int)

    with open(filename) as f:

        for i in range(0,32):

            linestr = f.readline()

            for j in range(0,32):

                vector[0,32*i+j] = int(linestr[j])

    return  vector

def compare(filename1,filename2):

    #compare直接讀取資源庫識別

    #filename1資源庫目錄，filename2 待識別圖像01txt文檔路徑

    trainingfilelist = os.listdir(filename1)

    m = len(trainingfilelist)

    labelvector = []

    trainingmatrix = numpy.zeros((m, 1024), numpy.int8)

    for i in range(0,m):

        filenamestr = trainingfilelist[i]

        filestr = filenamestr.split('.')[0]

        classnumber = int(filestr.split('_')[0])

        labelvector.append(classnumber)

        trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)

    textvector = imgvector(filename2)

    resultdistance = numpy.zeros((1,m))

    result = []

    for i in range(0,m):

        resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])

    resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)

    for i in resultindices:

        result.append(labelvector[i])

    number = Counter(result).most_common(1)

    print('此數字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))

def distinguish(filename1,filename2,filename3,size=(32,32)):

    # filename1 png，jpg等格式原始圖像路徑，filename2 原始圖像轉換成01txt文件路徑，filename3 資源庫路徑

    pictureconvert(filename1,filename2,size)

    compare(filename3,filename2)

url1 = "/Users/wang/Desktop/number.png"

url2 = "/Users/wang/Desktop/number.txt"

traininglibrary = "/Users/wang/Documents/trainingDigits"

distinguish(url1,url2,traininglibrary)

Ⅱ Python 機器學習 K-近鄰演算法 常用距離度量方法

在K-近鄰（KNN）演算法中，選擇合適的距離度量至關重要，因為它直接影響到數據點之間的「相似性」計算。不同距離度量可能導致模型性能差異。進行交叉驗證比較不同度量對模型的影響，以確定最佳選擇。下面列舉了幾種常用距離度量方法：

1. 歐幾里得距離（Euclidean Distance）
適用於連續型數據，是多維空間中兩點間的「直線」距離。計算方法如下：

- **使用math模塊**：
- **使用NumPy**：

2. 曼哈頓距離（Manhattan Distance）
在KNN中常用，衡量兩點在標准坐標繫上的絕對軸距總和。計算方法：

- **使用math模塊**：
- **使用NumPy**：

3. 切比雪夫距離（Chebyshev Distance）
特別適用於各維度相對重要性相同的情況，機器學習中用於KNN演算法，尤其在最大差異重要的場景。計算方法：

- **使用math模塊**：
- **使用NumPy**：

4. 閔可夫斯基距離（Minkowski Distance）
是歐幾里得距離和曼哈頓距離的推廣，用於KNN演算法時建議數據標准化或歸一化。計算方法：

- **使用math模塊**：
- **使用NumPy**：

5. 漢明距離（Hamming Distance）
用於度量相同長度序列的差異，常用於處理分類變數或二進制數據。計算方法：

- **使用math模塊**：
- **使用NumPy**：

6. scikit-learn中使用
在scikit-learn庫中，通過初始化K-近鄰（KNN）模型時設置metric參數來選擇不同的度量方法。示例代碼如下：

- **Python 機器學習 K-近鄰演算法 距離度量**：
- **詳細文檔**：

每種距離度量方法都有其適用場景，選擇時需考慮數據特性和問題需求。通過實驗比較不同度量對KNN模型性能的影響，有助於找到最優解決方案。