nknn演算法python實現

❶ knn演算法是什麼

KNN（K- Nearest Neighbor）法即K最鄰近法，最初由Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。

作為一種非參數的分類演算法，K-近鄰（KNN）演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。

介紹

KNN演算法本身簡單有效，它是一種lazy-learning演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為n，那麼KNN的分類時間復雜度為O(n)。

KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

❷ 新手學習python中KNN演算法的手寫識別出現問題 求助

參考了其他博主的代碼 想試著運行 然後去理解。結果一直報錯，希望大神幫幫忙。
import numpy as np
import os
import kNN

def img2vector(filename):
"""函數將以文本格式出現的32*32的0-1圖片，轉變成一維特徵數組，返回一維數組

Keyword argument:
filename -- 文本格式的圖片文件
"""

imgvect = np.zeros((1, 1024))
fr = open(filename)
for i in range(32):
linestr = fr.readline()
for j in range(32):
imgvect[0, 32*i + j] = int(linestr[j])
return imgvect

def handwriteClassfiy(testfile, trainfile, k):
"""函數將trainfile中的文本圖片轉換成樣本特徵集和樣本類型集，用testfile中的測試樣本測試，無返回值

Keyword argument:
testfile -- 測試圖片目錄
trainfile -- 樣本圖片目錄
"""

trainFileList = os.listdir(trainfile)
trainFileSize = len(trainFileList)
labels = []
trainDataSet = np.zeros((trainFileSize, 1024))
for i in range(trainFileSize):
filenameStr = trainFileList[i]
digitnameStr = filenameStr.split('.')[0]
digitLabels = digitnameStr.split('_')[0]
labels.append(digitLabels)
trainDataSet[i, :] = img2vector(trainfile + '/' + filenameStr)
testFileList = os.listdir(testfile)
testNumber = len(testFileList)
errorcount = 0.0
for testname in testFileList:
testdigit = img2vector(testfile + '/' + testname)
classifyresult = kNN.classfiy(testdigit, trainDataSet, labels, k)
testStr = testname.split('.')[0]
testDigitLabel = testStr.split('_')[0]
if classifyresult != testDigitLabel:
errorcount += 1.0
#print('this test real digit is：%s, and the result is: %s' % (testDigitLabel, classifyresult))
print('k = %d, errorRatio is: %f' % (k, errorcount/float(testNumber)))
return

if __name__ == '__main__':
filename = 'C:/Users/lx/Desktop/MachineLearning-master/kNN/use Python and NumPy/testDigits/0_1.txt'
traindir= 'C:/Users/lx/Desktop/MachineLearning-master/kNN/use Python and NumPy/trainingDigits'
testdir = 'C:/Users/lx/Desktop/MachineLearning-master/kNN/use Python and NumPy/testDigits'
handwriteClassfiy(testdir, traindir, 3)
錯誤提示Traceback (most recent call last):
File "kNN.py", line 56, in <mole>
handwriteClassfiy(testdir, traindir, 3)
File "kNN.py", line 43, in handwriteClassfiy
classifyresult = kNN.classfiy(testdigit, trainDataSet, labels, k)
AttributeError: mole 'kNN' has no attribute 'classfiy'
你這個文件是不是就叫 kNN.py ？如果是的話那你這個裡面根本就沒有 classfiy 這個屬性，當然會報錯。

另外，import kNN 是 import 自己？

❸ python 問題 實現KNN演算法

你好：
字面意思是：字典對象沒有屬性：iteritems；

你這是要遍歷什麼嗎？

❹ 在Python上Dry Beans用knn分類訓練集為70%測試集為30%的代碼怎麼寫

摘要 處理數據集數據 清洗，採用留出法hold-out拆分數據集：訓練集、測試集

❺ python計算每兩個向量之間的距離並保持到矩陣中

在很多演算法中都會涉及到求向量歐式距離，例如機器學習中的KNN演算法，就需要對由訓練集A和測試集B中的向量組成的所有有序對(Ai,Bi),求出Ai和Bi的歐式距離。這樣的話就會帶來一個二重的嵌套循環，在向量集很大時效率不高。
這里介紹如何將這一過程用矩陣運算實現。
假設有兩個三維向量集，用矩陣表示:

A=[a11a12a21a22a31a32]

B=⎡⎣⎢⎢b11b12b13b21b22b23b31b32b33⎤⎦⎥⎥

要求A，B兩個集合中的元素兩兩間歐氏距離。

先求出ABT：

ABT=⎡⎣⎢⎢⎢⎢⎢∑k=13ak1bk1∑k=13ak2bk1∑k=13ak1bk2∑k=13ak2bk2∑k=13ak1bk3∑k=13ak2bk3⎤⎦⎥⎥⎥⎥⎥

然後對A和BT分別求其中每個向量的模平方，並擴展為2*3矩陣：

Asq=⎡⎣⎢⎢⎢⎢⎢∑k=13(ak1)2∑k=13(ak2)2∑k=13(ak1)2∑k=13(ak2)2∑k=13(ak1)2∑k=13(ak2)2⎤⎦⎥⎥⎥⎥⎥

Bsq=⎡⎣⎢⎢⎢⎢⎢∑k=13(bk1)2∑k=13(bk1)2∑k=13(bk2)2∑k=13(bk2)2∑k=13(bk3)2∑k=13(bk3)2⎤⎦⎥⎥⎥⎥⎥

然後：

Asq+Bsq−2ABT=⎡⎣⎢⎢⎢⎢⎢∑k=13(ak1−bk1)2∑k=13(ak2−bk1)2∑k=13(ak1−bk2)2∑k=13(ak2−bk2)2∑k=13(ak1−bk3)2∑k=13(ak2−bk3)2⎤⎦⎥⎥⎥⎥⎥

將上面這個矩陣一開平方，就得到了A，B向量集兩兩間的歐式距離了。
下面是Python實現：
import numpy
def EuclideanDistances(A, B):
BT = B.transpose()
vecProd = A * BT
SqA = A.getA()**2
sumSqA = numpy.matrix(numpy.sum(SqA, axis=1))
sumSqAEx = numpy.tile(sumSqA.transpose(), (1, vecProd.shape[1]))
SqB = B.getA()**2
sumSqB = numpy.sum(SqB, axis=1)
sumSqBEx = numpy.tile(sumSqB, (vecProd.shape[0], 1))
SqED = sumSqBEx + sumSqAEx - 2*vecProd
ED = (SqED.getA())**0.5
return numpy.matrix(ED)

❻ python，knn演算法的筆跡識別，總有地方報錯，求大神幫忙

你想把這個參數的值列印出來，但參數並不存在，最簡單的方法，把這句列印的語句注釋掉

❼ python 如何畫出KD數

簡單的KNN演算法在為每個數據點預測類別時都需要遍歷整個訓練數據集來求解距離，這樣的做法在訓練數據集特別大的時候並不高效，一種改進的方法就是使用kd樹來存儲訓練數據集，這樣可以使KNN分類器更高效。
KD樹的主要思想跟二叉樹類似，我們先來回憶一下二叉樹的結構，二叉樹中每個節點可以看成是一個數，當前節點總是比左子樹中每個節點大，比右子樹中每個節點小。而KD樹中每個節點是一個向量(也可能是多個向量)，和二叉樹總是按照數的大小劃分不同的是，KD樹每層需要選定向量中的某一維，然後根據這一維按左小右大的方式劃分數據。在構建KD樹時，關鍵需要解決2個問題：（1）選擇向量的哪一維進行劃分（2）如何劃分數據。第一個問題簡單的解決方法可以是選擇隨機選擇某一維或按順序選擇，但是更好的方法應該是在數據比較分散的那一維進行劃分（分散的程度可以根據方差來衡量）。好的劃分方法可以使構建的樹比較平衡，可以每次選擇中位數來進行劃分，這樣問題2也得到了解決。下面是建立KD樹的Python代碼：
def build_tree(data, dim, depth):
"""
建立KD樹

Parameters
----------
data:numpy.array
需要建樹的數據集
dim:int
數據集特徵的維數
depth:int
當前樹的深度
Returns
-------
tree_node:tree_node namedtuple
樹的跟節點
"""
size = data.shape[0]
if size == 0:
return None
# 確定本層劃分參照的特徵
split_dim = depth % dim
mid = size / 2
# 按照參照的特徵劃分數據集
r_indx = np.argpartition(data[:, split_dim], mid)
data = data[r_indx, :]
left = data[0: mid]
right = data[mid + 1: size]
mid_data = data[mid]
# 分別遞歸建立左右子樹
left = build_tree(left, dim, depth + 1)
right = build_tree(right, dim, depth + 1)
# 返回樹的根節點
return Tree_Node(left=left,
right=right,
data=mid_data,
split_dim=split_dim)


對於一個新來的數據點x，我們需要查找KD樹中距離它最近的節點。KD樹的查找演算法還是和二叉樹查找的演算法類似，但是因為KD樹每次是按照某一特定的維來劃分，所以當從跟節點沿著邊查找到葉節點時候並不能保證當前的葉節點就離x最近，我們還需要回溯並在每個父節點上判斷另一個未查找的子樹是否有可能存在離x更近的點（如何確定的方法我們可以思考二維的時候，以x為原點，當前最小的距離為半徑畫園，看是否與劃分的直線相交，相交則另一個子樹中可能存在更近的點），如果存在就進入子樹查找。
當我們需要查找K個距離x最近的節點時，我們只需要維護一個長度為K的優先隊列保持當前距離x最近的K個點。在回溯時，每次都使用第K短距離來判斷另一個子節點中是否存在更近的節點即可。下面是具體實現的python代碼：
def search_n(cur_node, data, queue, k):
"""
查找K近鄰，最後queue中的k各值就是k近鄰

Parameters
----------
cur_node:tree_node namedtuple
當前樹的跟節點
data:numpy.array
數據
queue:Queue.PriorityQueue
記錄當前k個近鄰，距離大的先輸出
k:int
查找的近鄰個數
"""
# 當前節點為空，直接返回上層節點
if cur_node is None:
return None
if type(data) is not np.array:
data = np.asarray(data)
cur_data = cur_node.data
# 得到左右子節點
left = cur_node.left
right = cur_node.right
# 計算當前節點與數據點的距離
distance = np.sum((data - cur_data) ** 2) ** .5
cur_split_dim = cur_node.split_dim
flag = False # 標記在回溯時是否需要進入另一個子樹查找
# 根據參照的特徵來判斷是先進入左子樹還是右子樹
if data[cur_split_dim] > cur_data[cur_split_dim]:
tmp = right
right = left
left = tmp
# 進入子樹查找
search_n(left, data, queue, k)
# 下面是回溯過程
# 當隊列中沒有k個近鄰時，直接將當前節點入隊，並進入另一個子樹開始查找
if len(queue) < k:

neg_distance = -1 * distance
heapq.heappush(queue, (neg_distance, cur_node))
flag = True
else:
# 得到當前距離數據點第K遠的節點
top_neg_distance, top_node = heapq.heappop(queue)
# 如果當前節點與數據點的距離更小，則更新隊列（當前節點入隊，原第k遠的節點出隊）
if - 1 * top_neg_distance > distance:
top_neg_distance, top_node = -1 * distance, cur_node
heapq.heappush(queue, (top_neg_distance, top_node))
# 判斷另一個子樹內是否可能存在跟數據點的距離比當前第K遠的距離更小的節點
top_neg_distance, top_node = heapq.heappop(queue)
if abs(data[cur_split_dim] - cur_data[cur_split_dim]) < -1 * top_neg_distance:
flag = True
heapq.heappush(queue, (top_neg_distance, top_node))
# 進入另一個子樹搜索
if flag:
search_n(right, data, queue, k)525354555657

以上就是KD樹的Python實踐的全部內容，由於本人剛接觸python不久，可能實現上並不優雅，也可能在演算法理解上存在偏差，如果有任何的錯誤或不足，希望各位賜教。

❽ 如何用python實現knn演算法

1. 數據分類：離散型標簽 2. 數據回歸：連續型標簽 近鄰演算法的准則是：尋找接近新數據點的訓練樣本的數目，根據訓練樣本的信息來預測新數據點的某些信息。

❾ 誰可以提供Python環境中用KNN手寫識別數據MNIST的讀取代碼

其實就是python怎麼讀取binnary
file
mnist的結構如下，選取train-images
TRAINING
SET
IMAGE
FILE
(train-images-idx3-ubyte):
[offset]
[type]

[value]

[description]
0000

32
bit
integer
0x00000803(2051)
magic
number
0004

32
bit
integer
60000

number
of
images
0008

32
bit
integer
28

number
of
rows
0012

32
bit
integer
28

number
of
columns
0016

unsigned
byte

??

pixel
0017

unsigned
byte

??

pixel
........
xxxx

unsigned
byte

??

pixel
也就是之前我們要讀取4個
32
bit
integer
試過很多方法，覺得最方便的，至少對我來說還是使用
struct.unpack_from()
filename
=
'train-images.idx3-ubyte'binfile
=
open(filename
,
'rb')buf
=
binfile.read()
先使用二進制方式把文件都讀進來
index
=
0magic,
numImages
,
numRows
,
numColumns
=
struct.unpack_from('>IIII'
,
buf
,
index)index
+=
struct.calcsize('>IIII')
然後使用struc.unpack_from
'>IIII'是說使用大端法讀取4個unsinged
int32
然後讀取一個圖片測試是否讀取成功
im
=
struct.unpack_from('>784B'
,buf,
index)index
+=
struct.calcsize('>784B')
im
=
np.array(im)im
=
im.reshape(28,28)
fig
=
plt.figure()plotwindow
=
fig.add_subplot(111)plt.imshow(im
,
cmap='gray')plt.show()
'>784B'的意思就是用大端法讀取784個unsigned
byte
完整代碼如下
import
numpy
as
npimport
structimport
matplotlib.pyplot
as
plt
filename
=
'train-images.idx3-ubyte'binfile
=
open(filename
,
'rb')buf
=
binfile.read()
index
=
0magic,
numImages
,
numRows
,
numColumns
=
struct.unpack_from('>IIII'
,
buf
,
index)index
+=
struct.calcsize('>IIII')
im
=
struct.unpack_from('>784B'
,buf,
index)index
+=
struct.calcsize('>784B')
im
=
np.array(im)im
=
im.reshape(28,28)
fig
=
plt.figure()plotwindow
=
fig.add_subplot(111)plt.imshow(im
,
cmap='gray')plt.show()
只是為了測試是否成功所以只讀了一張圖片

❿ knn演算法算是一種python模型嗎

「演算法」不能算是「模型」，更不能說是「python模型」，因為python能實現的，c++、java等通用語言也能實現。