ML - KNN - 天天看點

文章目錄

- 一、本質
- - 示例說明
  - 計算流程
- 二、特點
- - 缺點：
- 三、超參數 & 模型參數
- - kNN 算法中的超參數
- 四、代碼實作
- - 1、Python 原生的實作
  - 2、sklearn 的實作
- 五、評估算法的準确性
- 六、digits 手寫數字識别
- 相關資料

一、本質

kNN：k-Nearest Neighbors，K近鄰

理論基礎：如果樣本A 和樣本B 足夠相似，就A 和 B 大機率屬于同一個類别。

如果A 和 n 個樣本相似，A 和n個樣本屬于同一個類别。

示例說明

K近鄰算法示例:

資料：兩類點方塊和三角
綠色的點屬于方塊還是三角呢?
K=3 還是 K=5? 結果一樣嗎?

ML - KNN

計算流程

計算已知類别資料集中的點與目前點的距離；
按照距離依次排序；
選取與目前點距離最小的K個點；
确定前K個點所在類别的出現機率；
傳回前K個點出現頻率最高的類别作為目前點預測分類；

二、特點

思想極度簡單；它是一種 lazy-learning 算法。易于了解，便于實作。
應用數學知識少（幾乎為0）；
效果好；
很适合入門機器學習；

更完整的刻畫機器學習應用的流程；

分類器不需要使用訓練集進行訓練，訓練時間複雜度為0。

可以解釋機器學習算法使用過程中的很多細節問題；

可以解決分類問題；
可以解決回歸問題，如預測房價、考試分數。

方法：找到距離最近的 k 個節點，計算他們的平均值，或者根據距離添權重重。
KNN分類的計算複雜度和訓練集中的文檔數目成正比。

也就是說，如果訓練集中文檔總數為n,那麼KNN的分類時間複雜度為O(n)。
K值的選擇，距離度量和分類決策規則是該算法的三個基本要素
KNN 不需要訓練過程，沒有産生模型；

為了和其他算法統一，可以認為訓練資料集就是模型本身。
sklearn 中對應的類：KNeighborsRegressor
應用場景：小資料場景，幾千到幾萬

缺點：

效率低下（最大的缺點）

如果訓練集有 m 個樣本，n 個特征，則預測每一個新的資料，需要 O(m*n) 的時間複雜度。

優化：使用樹結構：KD-Tree, Ball-Tree；即使如此，kNN 的效率依然非常低。
高度資料相關

相較其他機器學習算法，kNN 對 outlier 更加敏感。

已知執行個體的樣本分布不均勻，執行個體數量過多占主導位置
預測的結果不具有可解釋性。
維數災難

随着次元的增加，看似相近的兩個點之間的距離越來越大。處理高次元的資料，很容易産生維數災難。如下：
需要大量的空間來存儲已知執行個體。
必須指定K值，K值的選擇如果不當，會帶來資料分類不精确的問題。

維數	點	距離
1維	0到1的距離	1
2維	(0,0)到(1,1) 的距離	1.414
3維	(0,0,0)到(1,1,1)的距離	1.73
64維	(0,0…0)到(1,1…1)的距離	8
10000維	(0,0…0)到(1,1…1)的距離	100

維數災難解決方法：降維

三、超參數 & 模型參數

超參數：運作算法之前需要決定的參數

模型參數：算法過程中學習的參數

kNN 算法中沒有模型參數，k 是經典的超參數；

如何尋找好的超參數：

領域知識
經驗數值

如 kNN 中 k 的經典數值為5；但實際問題以實際為準。
試驗搜尋
K 值最好選奇數，因為偶數容易 55開；
不要選擇太小的K值，因為容易遇到異常值（噪聲）。
K值過大：容易受到數量的影響

關于資料的預處理

注意點：

1、連續變量進行預處理，進行資料标準化，對于無序的分類變量，需要生成啞變量

kNN 算法中的超參數

ML - KNN

如果隻考慮最鄰近節點，那麼附近藍色節點多于紅色節點，會被判斷為藍色節點；
但紅色距離它更近，是以需要将距離（距離的倒數）也考慮進去。 1 > 1/3 + 1/4
這樣還可以解決平票的問題；即四個節點時，兩藍兩紅。

怎麼取K值？

1、為了判别未知資料的類别，以所有的已知類别的執行個體作為參考

2、重要的步驟：計算未知執行個體與所有已知執行個體的距離

3、選擇參考的執行個體參數K

4、根據少數服從多數的原則，讓未知的執行個體歸類于K個最近鄰樣本中最多數的類别（投票法則）

四、代碼實作

1、Python 原生的實作

from math import sqrt
distances = []
for x_ train in X_train:
    d = sqrt(np. sum((x_ train - x)**2) ) 
    distances.append(d)

 # 排序後 原資料的索引
nearest = np.argsort(distance) 

k = 6
topK_y = [ y_train[i] for i in nearest[:k] ]

from collections import Counter

votes = Counter(topK_y)

votes.most_common(2) # 最多的資料

以上方法封裝

import numpy as np
from math import sqrt
from collections import Counter

def kNN_classify(k, X_train, y_train, x):
    assert 1 <= k <= X_train.shape[0], "k must be valid"
    assert X_train.shape[0] == y_train.shape [0], "the size of X_train must equal to the size of y_train"
    assert X_train.shape[1] == x.shape[0], "the feature number of x must be equal to X_train"
    distances = [sqrt(np.sum((x_train - x)**2)) for x_train in X_train ]
    nearest = np.argsort(distances)
    
    topK_y = [y_train[i] for i in nearest[:k]]
    votes = Counter(topK_y)
    return votes.most_common(1)[0][0]

2、sklearn 的實作

from sklearn.neighbors import KNeighborsClassifier
knn_cls = KNeighborsClassifier(n_neighbors=6)
knn_cls.fit(X_train, y_train) # 傳回 機器學習對象自身
X_predict = x.reshape(1, -1) # 将 x 轉化為矩陣，-1表示numpy 來決定多少列
# 預測，需要傳入矩陣
y_predict = knn_cls.predict(X_predict) # 得到向量
y_predict[0]

sklearn 調用方法的封裝

import numpy as np
from math import sqrt
from collections import Counter
from .metrics import accuracy_score

class KNNClassifier:

    def __init__(self, k):
        """初始化kNN分類器"""
        assert k >= 1, "k must be valid"
        self.k = k
        self._X_train = None
        self._y_train = None
    
    def fit(self, X_train, y_train):
        """根據訓練資料集X_train和y_train訓練kNN分類器"""
        assert X_train.shape[0] == y_train.shape[0], \
            "the size of X_train must be equal to the size of y_train"
        assert self.k <= X_train.shape[0], \
            "the size of X_train must be at least k."
    
        self._X_train = X_train
        self._y_train = y_train
        return self
    
    def predict(self, X_predict):
        """給定待預測資料集X_predict，傳回表示X_predict的結果向量"""
        assert self._X_train is not None and self._y_train is not None, "must fit before predict!"
        assert X_predict.shape[1] == self._X_train.shape[1],   "the feature number of X_predict must be equal to X_train"
    
        y_predict = [self._predict(x) for x in X_predict]
        return np.array(y_predict)
    
    # 給定單個待預測資料x，傳回x的預測結果值
    def _predict(self, x):
         
        assert x.shape[0] == self._X_train.shape[1],  "the feature number of x must be equal to X_train"
    
        distances = [sqrt(np.sum((x_train - x) ** 2))
                     for x_train in self._X_train]
        nearest = np.argsort(distances)
    
        topK_y = [self._y_train[i] for i in nearest[:self.k]]
        votes = Counter(topK_y)
    
        return votes.most_common(1)[0][0]
    
    # 根據測試資料集 X_test 和 y_test 确定目前模型的準确度
    def score(self, X_test, y_test): 
        y_predict = self.predict(X_test)
        return accuracy_score(y_test, y_predict)
    
    def __repr__(self):
        return "KNN(k=%d)" % self.k

五、評估算法的準确性

測試資料和訓練資料部分可參考：

my_knn_clf = KNNClassifier(k=3)
my_knn_clf.fit(X_train, y_train)
y_predict = my_knn_clf.predict(X_test)
sum(y_test == y_predict)/len(y_test) # 0.8666666666666667

以上評估方式也稱為分類的準确度 accuracy

六、digits 手寫數字識别

import numpy as np
from sklearn import datasets
import matplotlib.pyplot as plt
 
digits = datasets.load_digits()  # digits 是一個字典類型資料
 
digits
''' 
    {'data': array([[ 0.,  0.,  5., ...,  0.,  0.,  0.],
            [ 0.,  0.,  0., ..., 10.,  0.,  0.],
            ...,
            [ 0.,  0.,  1., ...,  6.,  0.,  0.],
            [ 0.,  0., 10., ..., 12.,  1.,  0.]]),
     'target': array([0, 1, 2, ..., 8, 9, 8]),
     'target_names': array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
     'images': array([[[ 0.,  0.,  5., ...,  1.,  0.,  0.],
             [ 0.,  0., 13., ..., 15.,  5.,  0.],
             ...,
             [ 0.,  4., 16., ..., 16.,  6.,  0.],
             [ 0.,  8., 16., ..., 16.,  8.,  0.],
             [ 0.,  1.,  8., ..., 12.,  1.,  0.]]]),
     'DESCR': ".. _digits_dataset:\n\nOptical recognition of handwritten digits dataset\n--------------------------------------------------\n\n**Data Set Characteristics:**\n\n    :Number of Instances: 5620\n    :Number of Attributes: 64\n    :Attribute Information: 8x8 image of integer pixels in the range 0..16.\n    :Missing Attribute Values: None\n    :Creator: E. Alpaydin (alpaydin '@' boun.edu.tr)\n    :Date: July; 1998\n\nThis is a copy of the test set of the UCI ML hand-written digits datasets\nhttps://archive.ics.uci.edu/ml/datasets/Optical+Recognition+of+Handwritten+Digits\n\nThe data set contains images of hand-written digits: 10 classes where\neach class refers to a digit.\n\nPreprocessing programs made available by NIST were used to extract\nnormalized bitmaps of handwritten digits from a preprinted form. From a\ntotal of 43 people, 30 contributed to the training set and different 13\nto the test set. 32x32 bitmaps are divided into nonoverlapping blocks of\n4x4 and the number of on pixels are counted in each block. This generates\nan input matrix of 8x8 where each element is an integer in the range\n0..16. This reduces dimensionality and gives invariance to small\ndistortions.\n\nFor info on NIST preprocessing routines, see M. D. Garris, J. L. Blue, G.\nT. Candela, D. L. Dimmick, J. Geist, P. J. Grother, S. A. Janet, and C.\nL. Wilson, NIST Form-Based Handprint Recognition System, NISTIR 5469,\n1994.\n\n.. topic:: References\n\n  - C. Kaynak (1995) Methods of Combining Multiple Classifiers and Their\n    Applications to Handwritten Digit Recognition, MSc Thesis, Institute of\n    Graduate Studies in Science and Engineering, Bogazici University.\n  - E. Alpaydin, C. Kaynak (1998) Cascading Classifiers, Kybernetika.\n  - Ken Tang and Ponnuthurai N. Suganthan and Xi Yao and A. Kai Qin.\n    Linear dimensionalityreduction using relevance weighted LDA. School of\n    Electrical and Electronic Engineering Nanyang Technological University.\n    2005.\n  - Claudio Gentile. A New Approximate Maximal Margin Classification\n    Algorithm. NIPS. 2000."}
''' 
 
digits.keys()
''' 
    dict_keys(['data', 'target', 'target_names', 'images', 'DESCR'])
''' 
 
digits.DESCR 

X = digits.data
y = digits.target
X.shape, y.shape
# ((1797, 64), (1797,))

digits.target_names
# array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
 
y[:100]
''' 
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1,
           2, 3, 4, 5, 6, 7, 8, 9, 0, 9, 5, 5, 6, 5, 0, 9, 8, 9, 8, 4, 1, 7,
           7, 3, 5, 1, 0, 0, 2, 2, 7, 8, 2, 0, 1, 2, 6, 3, 3, 7, 3, 3, 4, 6,
           6, 6, 4, 9, 1, 5, 0, 9, 5, 2, 8, 2, 0, 0, 1, 7, 6, 3, 2, 1, 7, 4,
           6, 3, 1, 3, 9, 1, 7, 6, 8, 4, 3, 1])
''' 
from sklearn.model_selection import train_test_split
 
X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.2, random_state=2) 
 
y_test.shape, y_train.shape
# ((360,), (1437,))
 
from sklearn.neighbors import KNeighborsClassifier
 
knn_cls = KNeighborsClassifier(n_neighbors=3)
knn_cls.fit(X_train, y_train) 
''' 
    KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
                         metric_params=None, n_jobs=None, n_neighbors=3, p=2,
                         weights='uniform')
''' 
y_predict = knn_cls.predict(X_test)
 
sum(y_predict == y_test)/len(y_test)
# 0.9888888888888889

from sklearn.metrics import accuracy_score
accuracy_score(y_test, y_predict)  # 0.9888888888888889

ML - KNN

文章目錄

一、本質

示例說明

計算流程

二、特點

缺點：

三、超參數 & 模型參數

kNN 算法中的超參數

四、代碼實作

1、Python 原生的實作

2、sklearn 的實作

五、評估算法的準确性

六、digits 手寫數字識别

相關資料

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

吳恩達 coursera ML 第七課總結+作業答案前言目錄正文模型表示作業答案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

XGBoost Plotting API以及GBDT組合特征實踐 XGBoost Plotting API以及GBDT組合特征實踐

極大似然法(ML)與最大期望法(EM)

解碼器用于語義分割：資料依賴的解碼可以實作靈活的特征聚合

2021-2025年中國運動療法（KT）帶行業市場供需與戰略研究報告

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希