Python實現K-近鄰演演算法的範例程式碼

2022-09-08 18:03:01

一、介紹

k-近鄰演演算法（K-Nearest Neighbour algorithm），又稱 KNN 演演算法，是資料探勘技術中原理最簡單的演演算法。

工作原理：給定一個已知標籤類別的訓練資料集，輸入沒有標籤的新資料後，在訓練資料集中找到與新資料最鄰近的 k 個範例，如果這 k 個範例的多數屬於某個類別，那麼新資料就屬於這個類別。簡單理解為：由那些離 X 最近的 k 個點來投票決定 X 歸為哪一類。

二、k-近鄰演演算法的步驟

（1）計算已知類別資料集中的點與當前點之間的距離；

（2）按照距離遞增次序排序；

（3）選取與當前點距離最小的 k 個點；

（4）確定前k個點所在類別的出現頻率；

（5）返回前 k 個點出現頻率最高的類別作為當前點的預測類別。

三、Python 實現

判斷一個電影是愛情片還是動作片。

電影名稱	搞笑鏡頭	擁抱鏡頭	打鬥鏡頭	電影型別
0	功夫熊貓	39	0	31	喜劇片
1	葉問3	3	2	65	動作片
2	倫敦陷落	2	3	55	動作片
3	代理情人	9	38	2	愛情片
4	新步步驚心	8	34	17	愛情片
5	諜影重重	5	2	57	動作片
6	功夫熊貓	39	0	31	喜劇片
7	美人魚	21	17	5	喜劇片
8	寶貝當家	45	2	9	喜劇片
9	唐人街探案	23	3	17	？

歐氏距離

構建資料集

rowdata = {
    "電影名稱": ['功夫熊貓', '葉問3', '倫敦陷落', '代理情人', '新步步驚心', '諜影重重', '功夫熊貓', '美人魚', '寶貝當家'],
    "搞笑鏡頭": [39,3,2,9,8,5,39,21,45],
    "擁抱鏡頭": [0,2,3,38,34,2,0,17,2],
    "打鬥鏡頭": [31,65,55,2,17,57,31,5,9],
    "電影型別": ["喜劇片", "動作片", "動作片", "愛情片", "愛情片", "動作片", "喜劇片", "喜劇片", "喜劇片"]
}

計算已知類別資料集中的點與當前點之間的距離

new_data = [24,67]
dist = list((((movie_data.iloc[:6,1:3]-new_data)**2).sum(1))**0.5)

將距離升序排列，然後選取距離最小的 k 個點「容易擬合·以後專欄再論」

k = 4
dist_l = pd.DataFrame({'dist': dist, 'labels': (movie_data.iloc[:6, 3])}) 
dr = dist_l.sort_values(by='dist')[:k]

確定前 k 個點的類別的出現概率

re = dr.loc[:,'labels'].value_counts()
re.index[0]

選擇頻率最高的類別作為當前點的預測類別

result = []
result.append(re.index[0])
result

四、約會網站配對效果判定

# 匯入資料集
datingTest = pd.read_table('datingTestSet.txt',header=None)
datingTest.head()

# 分析資料
%matplotlib inline
import matplotlib as mpl
import matplotlib.pyplot as plt

#把不同標籤用顏色區分
Colors = []
for i in range(datingTest.shape[0]):
    m = datingTest.iloc[i,-1]  # 標籤
    if m=='didntLike':
        Colors.append('black')
    if m=='smallDoses':
        Colors.append('orange')
    if m=='largeDoses':
        Colors.append('red')

#繪製兩兩特徵之間的散點圖
plt.rcParams['font.sans-serif']=['Simhei'] #圖中字型設定為黑體
pl=plt.figure(figsize=(12,8))  # 建立一個畫布

fig1=pl.add_subplot(221)  # 建立兩行兩列畫布，放在第一個裡面
plt.scatter(datingTest.iloc[:,1],datingTest.iloc[:,2],marker='.',c=Colors)
plt.xlabel('玩遊戲視訊所佔時間比')
plt.ylabel('每週消費冰淇淋公升數')

fig2=pl.add_subplot(222)
plt.scatter(datingTest.iloc[:,0],datingTest.iloc[:,1],marker='.',c=Colors)
plt.xlabel('每年飛行常客里程')
plt.ylabel('玩遊戲視訊所佔時間比')

fig3=pl.add_subplot(223)
plt.scatter(datingTest.iloc[:,0],datingTest.iloc[:,2],marker='.',c=Colors)
plt.xlabel('每年飛行常客里程')
plt.ylabel('每週消費冰淇淋公升數')
plt.show()


# 資料歸一化
def minmax(dataSet):
    minDf = dataSet.min()
    maxDf = dataSet.max()
    normSet = (dataSet - minDf )/(maxDf - minDf)
    return normSet

datingT = pd.concat([minmax(datingTest.iloc[:, :3]), datingTest.iloc[:,3]], axis=1)
datingT.head()

# 切分訓練集和測試集
def randSplit(dataSet,rate=0.9):
    n = dataSet.shape[0] 
    m = int(n*rate)
    train = dataSet.iloc[:m,:]
    test = dataSet.iloc[m:,:]
    test.index = range(test.shape[0])
    return train,test

train,test = randSplit(datingT)


# 分類器針對約會網站的測試程式碼
def datingClass(train,test,k):
    n = train.shape[1] - 1  # 將標籤列減掉
    m = test.shape[0]  # 行數
    result = []
    for i in range(m):
        dist = list((((train.iloc[:, :n] - test.iloc[i, :n]) ** 2).sum(1))**5)
        dist_l = pd.DataFrame({'dist': dist, 'labels': (train.iloc[:, n])})
        dr = dist_l.sort_values(by = 'dist')[: k]
        re = dr.loc[:, 'labels'].value_counts()
        result.append(re.index[0])
    result = pd.Series(result)  
    test['predict'] = result  # 增加一列
    acc = (test.iloc[:,-1]==test.iloc[:,-2]).mean()
    print(f'模型預測準確率為{acc}')
    return test


datingClass(train,test,5)  # 95%

五、手寫數位識別

import os


#得到標記好的訓練集
def get_train():
    path = 'digits/trainingDigits'
    trainingFileList = os.listdir(path)
    train = pd.DataFrame()
    img = []  # 第一列原來的影象轉換為圖片裡面0和1，一行
    labels = []  # 第二列原來的標籤
    for i in range(len(trainingFileList)):
        filename = trainingFileList[i]
        txt = pd.read_csv(f'digits/trainingDigits/{filename}', header = None) #32行
        num = ''
        # 將32行轉變為1行
        for i in range(txt.shape[0]):
            num += txt.iloc[i,:]
        img.append(num[0])
        filelable = filename.split('_')[0]
        labels.append(filelable)
    train['img'] = img
    train['labels'] = labels
    return train
    
train = get_train()   



# 得到標記好的測試集
def get_test():
    path = 'digits/testDigits'
    testFileList = os.listdir(path)
    test = pd.DataFrame()
    img = []  # 第一列原來的影象轉換為圖片裡面0和1，一行
    labels = []  # 第二列原來的標籤
    for i in range(len(testFileList)):
        filename = testFileList[i]
        txt = pd.read_csv(f'digits/testDigits/{filename}', header = None) #32行
        num = ''
        # 將32行轉變為1行
        for i in range(txt.shape[0]):
            num += txt.iloc[i,:]
        img.append(num[0])
        filelable = filename.split('_')[0]
        labels.append(filelable)
    test['img'] = img
    test['labels'] = labels
    return test

test = get_test()

# 分類器針對手寫數位的測試程式碼
from Levenshtein import hamming

def handwritingClass(train, test, k):
    n = train.shape[0]
    m = test.shape[0]
    result = []
    for i in range(m):
        dist = []
        for j in range(n):
            d = str(hamming(train.iloc[j,0], test.iloc[i,0]))
            dist.append(d)
        dist_l = pd.DataFrame({'dist':dist, 'labels':(train.iloc[:,1])})
        dr = dist_l.sort_values(by='dist')[:k]
        re = dr.loc[:,'labels'].value_counts()
        result.append(re.index[0])
    result = pd.Series(result)
    test['predict'] = result
    acc = (test.iloc[:,-1] == test.iloc[:,-2]).mean()
    print(f'模型預測準確率為{acc}')
    return test

handwritingClass(train, test, 3)  # 97.8%